| | | |
| Small keys: |
| Smooth |
| QS |
| NFS |
|
|
Finding smooth numbers
Algorithms such as
QS
and
NFS
factor N in four steps:
- generating a huge pile of random-looking auxiliary numbers related to N;
- relation search:
searching through the pile of auxiliary numbers
for numbers that are easy to factor;
- linear algebra:
using those factorizations to find a bunch of auxiliary numbers
whose product is a square;
- using this square to figure out the factorization of N.
Relation search is the most important step.
The easiest numbers to factor are smooth numbers,
i.e., numbers that factor into small primes.
There are several ways to quickly find these smooth numbers (and their factorizations):
The following Sage code uses batch trial division to find smooth numbers,
and does a little extra work to make a list of the primes dividing each smooth number.
The code also finds smooth numbers times squares,
and suppresses squares of primes in the output,
so each prime appears only once for each number.
def oddpowers(P,x):
if len(P) == 0: return [[],x,x]
P = primesin(P,x)
e,r,x = oddpowers([p*p for p in P],x)
Q = primesin(P,r)
return [Q,r / product(Q),x]
def oddpowersineach(P,X):
return [oddpowers(Q,x) for Q,x in zip(primesineach(P,X),X)]
def easilyfactorable(x,pmodx):
smoothpart = Mod(pmodx,x)^x.nbits()
return (x / gcd(x,Integer(smoothpart))).is_square()
def easyfactorizations(P,X):
result = zip(X,remainders(product(P),X))
result = [x for x,pmodx in result if easilyfactorable(x,pmodx)]
return oddpowersineach(P,result)
# example:
print easyfactorizations([2,3,5,7],[50,157,266,377,490,605])
# output: [[[2], 1, 50], [[2, 5], 1, 490], [[5], 121, 605]]
Version:
This is version 2012.12.28 of the smooth.html web page.
|