Paolo Ardoino - ideas, programming, web and more…

[This article appeared on OndaQuadra0A Elettronic Magazine]

Fondamenti di Matematica - Algoritmi Fondamentali

Metodo delle curve ellittiche per la fattorizzazione

di numeri interi.

by Paolo Ardoino AKA binduck < paolo.ardoino@gmail.com >

< http://ardoino.com >
Prima di passare al prossimo algoritmo per la riduzione in fattori

primi di un numero, conviene spiegare alcuni concetti matematici

e alcuni algoritmi che stanno alla base delle operazioni tra numeri

interi composti da molte cifre.

N.B. Questi sono solo riassunti basilari e molto semplici, che potete

consultare per avere un idea delle nozioni che sono richieste negli

articoli matematico-informatici. Per una completa visione di questi

leggete testi di matematica e algoritmi.

Mi raccomando ricordate che la matematica e’ molto importante se

volete tuffarvi nel campo della crittografia.

Le implementazioni degli algoritmi presentati in questo articolo

possono essere facilmente trovate in ogni libreria matematica per

qualsiasi linguaggio di programmazione.
0] Notazione usata
1] Concetti fondamentali
1.1] Matematica

1.1.1] Strutture algebriche

1.1.2] Gruppo

1.1.3] Anello

1.1.4] Campo

1.1.5] Aritmetica modulare

1.1.6] Piccolo teorema di Fermat
1.2] Informatica

1.2.1] Calcolabilita’ e complessita’ di un algoritmo

1.2.2] Rappresentazione numerica di un messaggio

1.2.3] Rappresentazione di un messaggio in Zn
2] Algoritmi fondamentali

2.1] Test di primalita’ e teorema di Fermat

2.1.1] Probabilistic primality test

2.2] Numeri random

2.2.1] Linear congruential method

2.3] Massimo comun divisore GCD
3] Elliptic Curve Method

 Read more »

    

This simple C program shows how to generate random prime numbers using openssl bignum libraries; it takes as argument the length of the primes in bits.Here’s the source Read more »

It is a number theoretic integer factorization algorithm, invented by John Pollard in 1974. It is a special-purpose algorithm, meaning that it is only suitable for integers with specific types of factors; it is the simplest example of an algebraic-group factorisation algorithm.

From Wikipedia

Pollard p-1 algorithm

1. N > 2
2. b = ( a finite integer )
3. Let k be a multiple of all (or nearly all) integers <= b ( i.e k = b )
4. 2 <= a <= N - 2 ( with a random )
5. Compute Greatest Common Divisor (GCD) between a^k-1(mod N) and N
   • So we need to comput a^k-1 in ZN and to find the Greatest Common Divisor between this value and N ( i.e : use the Euclid’s algorithm )
6. If GCD = 1 then return to 4. ; else if GCD > 1 then GCD is a prime number and we found a factor of N

Read more »

RSA strength depends on the difficulty to find prime factors of large integers and this is why these kind of algorithms gain a lot of attention.
Take an RSA key of 512 bits [ RSA-512 ]….
Read more »