Paolo Ardoino – ideas, programming, web and more…

This is a summarizing post of large integers factorization methods I have exposed in my articles.

•  Classical method
  • Source code
  • Results
• Pollard P-1
  • Source code
  • Results
• Elliptic curve method
  • Source code , Factor base
  • Results

[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 »