Dixon's Implementation In Java For Prime Number Factorization
Mark
Indirectly, you can use a genetic algorithm to factor an integer N. Dixon's integer factorization method uses equations involving powers of the first k primes, modulo N. These products of powers of small primes are called "smooth". If we are using the first k=4 primes - 2,3,5,7 - 42=2x3x7 is smooth and 11 is not (for lack of a better term, 11 is "rough"). Dixon's method requires an invertible k x k matrix consisting of the exponents that define these smooth numbers. For more on Dixon's method see _factorization_method.
B-Smooth: A positive integer is called B-Smooth if none of its prime factors is greater than B. For example:720 has prime factorization as 24 * 32 * 51 Therefore 720 is 5 smooth because none of its prime factors is greater than 5.
The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second-fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve.[1]
So the problem has now been reduced to: given a set of integers, find a subset whose product is a square. By the fundamental theorem of arithmetic, any positive integer can be written uniquely as a product of prime powers. We do this in a vector format; for example, the prime-power factorization of 504 is 23325071, it is therefore represented by the exponent vector (3,2,0,1). Multiplying two integers then corresponds to adding their exponent vectors. A number is a square when its exponent vector is even in every coordinate. For example, the vectors (3,2,0,1) + (1,0,0,1) = (4,2,0,2), so (504)(14) is a square. Searching for a square requires knowledge only of the parity of the numbers in the vectors, so it is sufficient to compute these vectors mod 2: (1,0,0,1) + (1,0,0,1) = (0,0,0,0).So given a set of (0,1)-vectors, we need to find a subset which adds to the zero vector mod 2.
This is a linear algebra problem since the ring Z / 2 Z \displaystyle \mathbb Z /2\mathbb Z can be regarded as the Galois field of order 2, that is we can divide by all non-zero numbers (there is only one, namely 1) when calculating modulo 2.It is a theorem of linear algebra that with more vectors than each vector has entries, a linear dependency always exists. It can be found by Gaussian elimination.However, simply squaring many random numbers mod n produces a very large number of different prime factors, and so very long vectors and a very large matrix. The trick is to look specifically for numbers a such that a2 mod n has only small prime factors (they are smooth numbers). They are harder to find, but using only smooth numbers keeps the vectors and matrices smaller and more tractable. The quadratic sieve searches for smooth numbers using a technique called sieving, discussed later, from which the algorithm takes its name.
Another way to increase the chance of smoothness is by simply increasing the size of the factor base. However, it is necessary to find at least one smooth relation more than the number of primes in the factor base, to ensure the existence of a linear dependency.
The sieve starts by setting every entry in a large array A[] of bytes to zero. For each p, solve the quadratic equation mod p to get two roots α and β, and then add an approximation to log(p) to every entry for which y(x) = 0 mod p ... that is, A[kp + α] and A[kp + β]. It is also necessary to solve the quadratic equation modulo small powers of p in order to recognise numbers divisible by small powers of a factor-base prime.
If, after dividing by all the factors less than A, the remaining part of the number (the cofactor) is less than A2, then this cofactor must be prime. In effect, it can be added to the factor base, by sorting the list of relations into order by cofactor. If y(a) = 7*11*23*137 and y(b) = 3*5*7*137, then y(a)y(b) = 3*5*11*23 * 72 * 1372. This works by reducing the threshold of entries in the sieving array above which a full factorization is performed.
To illustrate typical parameter choices for a realistic example on a real implementation including the multiple polynomial and large prime optimizations, the tool msieve was run on a 267-bit semiprime, producing the following parameters:
Until the discovery of the number field sieve (NFS), QS was the asymptotically fastest known general-purpose factoring algorithm. Now, Lenstra elliptic curve factorization has the same asymptotic running time as QS (in the case where n has exactly two prime factors of equal size), but in practice, QS is faster since it uses single-precision operations instead of the multi-precision operations used by the elliptic curve method.
On April 2, 1994, the factorization of RSA-129 was completed using QS. It was a 129-digit number, the product of two large primes, one of 64 digits and the other of 65 digits. The factor base for this factorization contained 524339 primes. The data collection phase took 5000 MIPS-years, done in distributed fashion over the Internet. The data collected totaled 2GB. The data processing phase took 45 hours on Bellcore's (now Telcordia Technologies) MasPar (massively parallel) supercomputer. This was the largest published factorization by a general-purpose algorithm, until NFS was used to factor RSA-130, completed April 10, 1996. All RSA numbers factored since then have been factored using NFS.
The program uses local storage to remember the progress of factorization, so you can complete the factorization of a large number in several sessions. Your computer will remember the state of the factorization, so you only have to reload this page.
Even though the value of the group order is difficult to find, it can be shown that it is near the prime number used as the modulus. By changing the curve, we obtain a different group, and its order also changes.
In the first step of the algorithm, we multiply points by powers of different prime numbers less than a bound named B1. By computing the greatest common divisor between the coordinate x of the computed point and the number to factor, we can obtain the prime factor of n, provided that all prime factors of the group order are less than B1.
Using the result of the first step, the second step obtains multiples of that point up to the upper bound B2. We then multiply the x-coordinates of all the points found in this step. Finally, we compute the greatest common divisor between the product and the number to factor. In this case, we can obtain the prime number we are searching for if all prime factors (except one) of the group order are less than B1, and the greatest prime factor of the group order is less than B2.
The ECM factoring algorithm can be easily parallelized in several machines. In order to do it, run the factorization in the first computer from curve 1, run it in the second computer from curve 10000, in the third computer from curve 20000, and so on.In order to change the curve number when a factorization is in progress, press the button named More, type this number on the input box located on the new window and press the New Curve button.
The relations found are combined using multiplications. The left-hand side will always be a square because it is a product of squares, so the goal is to have a square at the right-hand side. A number is a square when all its prime factors appear an even number of times.
The large prime SIQS uses large primes along with the factor base. The size of the largest prime depends on the number to be factored, but normally it is about 50 to 100 times larger than the greatest element of the factor base.
When the number to be factorized is in the range 31 to 95 digits, after computing some curves in order to find small factors, the program switches to SIQS (if the checkbox located below the applet enables it), which is an algorithm that is much faster than ECM when the number has two large prime factors.Since this method needs a large amount of your computer's memory to store relations, if you restart the applet the factorization begins from scratch. In order to start factoring immediately using SIQS, you can enter 0 in the New Curve box.
Example 2: Find the Smith numbers less than 10000. A Smith number, according to Wikipedia, is a composite number for which, in a given base (in base 10 by default), the sum of its digits is equal to the sum of the digits in its prime factorization.The line to type is: x=1;x=x+1;x
To factorize a small integer n using mental or pen-and-paper arithmetic, the simplest method is trial division: checking if the number is divisible by prime numbers 2, 3, 5, and so on, up to the square root of n. For larger numbers, especially when using a computer, various more sophisticated factorization algorithms are more efficient. A prime factorization algorithm typically involves testing whether each factor is prime each time a factor is found.
When the numbers are sufficiently large, no efficient non-quantum integer factorization algorithm is known. However, it has not been proven that such an algorithm does not exist. The presumed difficulty of this problem is important for the algorithms used in cryptography such as RSA public-key encryption and the RSA digital signature.[1] Many areas of mathematics and computer science have been brought to bear on the problem, including elliptic curves, algebraic number theory, and quantum computing.
Not all numbers of a given length are equally hard to factor. The hardest instances of these problems (for currently known techniques) are semiprimes, the product of two prime numbers. When they are both large, for instance more than two thousand bits long, randomly chosen, and about the same size (but not too close, for example, to avoid efficient factorization by Fermat's factorization method), even the fastest prime factorization algorithms on the fastest computers can take enough time to make the search impractical; that is, as the number of digits of the integer being factored increases, the number of operations required to perform the factorization on any computer increases drastically.
aa06259810