Talk:Dixon's factorization method

Comment

I cannot see a real difference to the Quadratic Sieve, but thar does not really matter.

Dixon's method is not a well-specified algorithm in that it doesn't really give a method for finding relations (presumably, brute-force search would be used). The quadratic sieve uses some mathematical facts and the sieving procedure to speed up the finding of relations. The number field sieve is yet another way of finding relations. Decrypt3 20:47, 24 March 2006 (UTC)

The confusion between Dixon's method and quadratic sieve is something I encounter increasingly frequently in the wild. I once saw a video on YouTube where a guy explains Dixon's method in great detail, all the while believing he is explaining quadratic sieve. Then just today I found another video on the same topic by the same guy, with the same mistake. And it's in this article too, where it asserts that the strength of QS is in finding small values of k^2 mod N, while its actual strength is in avoiding separate factorization of each candidate, and in spending very little time on dealing with failing candidates. I plan to fix this tomorrow. Rulatir (talk) 00:01, 21 October 2021 (UTC)

Question

I didn't understand this sentence: "This set of primes is called the factor base. Then, using the polynomial p(x) = x2 − n, many values of x are tested to see if p(x) factors completely over the factor base."

What is x? What is n? What does it mean to factor "over the factor base"?

n is the semi-prime which we are trying to factor x is one of many random numbers generated to try and find a p(x) which the prime factorization is contained in the factor base. for example if x=20 The prime factorization of 20 is: 2*2*5 If our factor base is [2,3,5] then p(x) factors completley or is "smooth" over our factor base.

I'm curious though is p(x)=x^2-n suposed to be p(x)=x^2 (mod n)

References

The references should be added to this page. Also, an expert is needed to say a few words about the history. Which Dixon is this one? Mhym 18:13, 24 June 2006 (UTC)

Overlap

This article has quite a bit of overlap with quadratic sieve, which also goes into quite a bit of detail regarding the linear algebra stage. This should be either in one or the other, or moved out to congruence of squares. Dcoetzee 02:47, 19 May 2007 (UTC)

Example is slightly faked

When testing N=84923 one actully find first b-smooth z=436, 436^2 mod N = 20250, which is 2*3^4*5^3.

Another important fact is that, we find in this example z=505 (less than "first" 513), is square 505^2 mod N = 256, which is 2^8. So whole procedure is somehow useless.

Maybe slightly better number N could be find to better ilustrate its application of Dixon's method.

--149.156.82.207 (talk) 20:36, 8 December 2010 (UTC)

I noticed this independently as well, but consider it a minor issue overall (compared to other things I'm trying to fix). Education uses contrived examples all the time.

If I do a search for a better choice of N later, I will want to find one where the first success requires combining three values rather than two. (so that the identification of linear dependence is not so trivial) --jandew (talk) 05:31, 2 June 2026 (UTC)

I have run a search for more appropriate N. And now need to sleep.

If prioritizing small factors for N (in the range of 100-200), then consider:

$N=24511=127\cdot 193$ for which the first three rows of

:⎡1  1  0  3⎤
:⎢1  4  2  0⎥
:⎢0  1  4  1⎥
:⎢1  0  0  4⎥
:⎣3  1  0  3⎦

with $Z=\{163,169,194,232,326\}$ produce $x=720,y=12107,\gcd(x+y,N)=127$ --jandew (talk) 08:48, 2 June 2026 (UTC)

Reference for running time?

What is the reference for the running time of L[1/2, 2sqrt(2)] claimed in the article? In Dixon's paper the time is stated as L[1/2, 3sqrt(2)], while Pomerance arrives at L[1/2, 2] for the plain method in (bound is claimed to be sharp there). --2003:51:4F60:6F01:D056:A97A:7C5F:91ED (talk) 19:38, 11 December 2014 (UTC)

Why start at 1 rather than sqrt(N)?

I understand that the pseudocode section is taken directly from literature that, for simplicity sake, framed the iteration as running over every value from 1 to N, but in practice, this is ridiculous. I feel like something somewhere in this article should mention skipping to start at sqrt(N). Is a reference needed?

To argue the point mathematically...

Every single result less than sqrt(N) is one which has a square less than N, thus it can never produce a nontrivial perfect square mod N. Moreover, it's useless collecting into the list, as its products with other elements of the list can only work if the other elements worked on their own already. This is because those less than sqrt(N) are B-smooth as normal integers, so they don't add any knowledge to the structure of integers mod N.

If such results did actually matter, then instead of iterating over the positive integers and attempting to factor them, we would simply generate these B-smooth integers by iterating over vectors of exponents on primes up to B, explicitly producing every such result. For example, the 3-smooth integers in any mod begin 2, 3, 2^2, 2*3, 2^3, 3^2, 2^2*3, etc. You can just generate those up to sqrt(N) to get all the results up to that point. --jandew (talk) 05:48, 2 June 2026 (UTC)

Incomplete timeline

I initially found my way to this page from Continued fraction factorization, which says it was described in 1931, implemented as a computer algorithm in 1975, and is based on Dixon's method. Then I arrive at this article to find that it was published in 1981.

Sounds to me like there's more dates to be added to this article to flesh out its development prior to 1931.--jandew (talk) 06:03, 2 June 2026 (UTC)

Major edits to step-by-step example

I've been making a collection of almost-minor edits to the page, particularly to the step-by-step example, also changing it to be described as "lightly adapted" rather than "lifted" from the referenced Substack document. So many correspondences with the pseudocode section were not clear, as well as a lot of formatting issues.

Now I'm about to make a major edit to the step-by-step example, so I'm preemptively starting this talk section to highlight that if it needs to be reverted, you don't need to revert all the semi-minor changes from before. And to give my reasoning, of course.

The issues I'm trying to fix now are regarding Step 5, Parts 1 and 2. These are when x and y are computed, respectively, and they are muddled. Part 1 includes prime factorizations that are only relevant to computing y, not x. There's logical flow / transition words in the math blocks, essentially using an align environment as a paragraph. With "double spacing" provided by extra newlines.

No other Wikipedia math page I've seen has done this. It appears to have been borrowed from the reference Substack document, as were other typographical oddities I've fixed in less potentially controversial ways. As I rework Step 5, I believe this is the appropriate time to reword "lightly adapted" as simply "adapted". If we go on to change the example N to a better choice, I imagine that will be the point to say "heavily adapted". Until structural edits are made (reordering, combining/separating parts) I still see it as "adapted from" rather than "inspired by". --jandew (talk) 06:24, 2 June 2026 (UTC)

I forgot to mention that Step 5, Part 1 mentions taking the square root, which is never actually done. The product of the z-values immediately produces the supposed square root. — Preceding unsigned comment added by Jandew (talk • contribs) 06:32, 2 June 2026 (UTC)