John D’s Dixon’s Algorithm

Good Day to all tech Geeks. In this blog, I am going to explain all the nitty grits of Dixon’s Algorithm. This magical factorization algorithm is typically used to evaluate the factors of composite numbers. Do not stress over it, everything is explained in this article.

Dixon’s Algorithm is an integer factorization algorithm. Dixon’s Algorithm is basically based on a number-theoretical notion that:

About Dixon’s Algorithm

Dixon’s Algorithm is based on an integer factorization algorithm. It’s the standard factor approach. The only component base approach with a known run-time bound that is not based on conjectures about the smoothness characteristics of polynomial values.

Their technique of Dixon is based on the discovery of asymmetry of squares modulo the number. We can find a congruence using Fermat’s factorization process by selecting pseudo-random entries and wishing that a2 mod N is a square.

NOTE:

a2 = b2 ( mod n) with ≠ ± b (mod n)

(it is most possible that gcd(a-b, n) would be a factor of n)

History of Dixon’s Algorithm

The integer factorization technique that carries his name was invented by John D. Dixon, a phenomenal mathematician at Carleton University, in the year 1981. Dixon’s algorithm isn’t used in practice because it’s slow, but it’s significant in pure mathematics because it’s the only sub-exponential estimating algorithm with a deterministic run time, and it’s the precursor to the quadratic sieve factorization method, which is extremely practical.

Micheal and John Brillhart discovered and published this method in 1975. When Dixon published his 1981 study, he didn’t know the complete story, but he did incorporate it in a later article. In what appears to be a recurring theme, major cryptology work from the last 38 years is highlighted. Dixon’s first piece, published in 1981, was rejected by the publication to which he submitted it. Dixon did not claim that the randomized version he presented would be comparable in reality with currently used algorithms.

Dixon’s Algorithm Step-by-Step:

Step 1:

Pick a good bound B and find all primes with a factor base (P) < or = B.

Step 2:

Find a positive integer c that is such that c2 mod(n) is B-Smooth.

C2 = || pi∈P Pia (mod n)

B-Smooth: A + integer is described as B-Smooth if not any of its main attributes exceeds B.

Step 3:

After producing a sufficient quantity of these relations (usually a few greater than the size of that certain P), we combine them using a linear algebra method (e.g. Gaussian Elimination). This technique should be repeated until we have a significant amount of smooth squares.

Step 4:

We get the following equation after multiplying all of these relationships:

x2 = y2 mod(N)

Step 5:

As a result, the elements in the equation above could be computed as follows:

GCD(x — y, N), GCD(x + y, N)

Execution

• For example, suppose we would like to factor N = 23449 with constraint B = 7. As a result, the factor base P equals 2, 5, 3, 7.
• a = ceil(sqrt(n)) = 154 in this case. As a result, we search at random for integers among 154 and N using B-Smooth square.
• A + integer is usually called B-Smooth if none of its main components is more than B, as previously stated. So, let’s assume we identify two digits, 970 & 8621, that have no prime numbers bigger than 7 in any of their squares.
• The following are the first comparable squares we get:
• 9702 % 23499 = 2940 = 22 * 3 * 5 * 7286212 % 23499 = 11760 = 24 * 3 * 5 * 72
• So, (8621 * 970)2 = (23 * 5 * 72* 3)2 % 23499. That gives:

142562 = 58802 % 23499.

After that, we get:

gcd(14256–5880, 23449) = 131

gcd(14256 + 5880, 23449) = 179

Thus, the factors we get are:

N = 131 * 179

Optimizations

Dixon’s approach has been improved with the quadratic sieve. Dixon’s clever factoring method was enhanced the year after it was first published. While at the University of Georgia, Carl Pomerance presented his technique, the Quadratic Sieve, in 1981.

It chooses x values that are close to the scale factor of N and have a small x 2 modulo N, greatly boosting the chances of getting a smooth number. The 7 Quadratic Sieve only examines primes in S that have a quadratic residue of n, whereas Dixon’s technique blindly attempts to factor every f(x) over the prime basis S.

n = t2 (mod p)

This is a considerably faster version of Dixon’s Method, and it is the fastest technique for factoring integers with much less than 115 decimal numbers.

Another technique to improve Dixon’s method of the algorithm is to use an improved algorithm for solving all types of matrix equations, which makes use of the matrix’s sparseness: a variable z can only have log2z factors, therefore each grid cell is almost entirely zeros. The block Lanczos method is commonly used in practice. Furthermore, the extent of the component base should be wisely selected: if it is very small, finding numbers that factorize entirely over it will be difficult, and if it is too high, more connections will have to be gathered.

Conclusion

We covered how to use Dixon’s Algorithm method for prime factorization in this blog. This method can be executed in parallel by numerous machines, which improves efficiency and makes it a good approach for factoring very big numbers.