Project Logs

Collapse

• Sieving versus checking

  kbsriram • 2 days ago • 0 comments

  Got these three ATtiny412s and a Pico to factor 5,283,065,753,709,209 - the number D.H. Lehmer's gear machine factored in 1932.

  The sieve scanned 5.6 million candidates in 113 seconds and rejected 87% of them. The Pico spent 23 minutes testing the 740,000 that survived. The sieve is idle for 92% of the run, waiting for the Pico to check survivors.

  So a sieve which scans ten times faster than Lehmer's 1932 gear machine, takes about as long to factor the same number. The difference is the number of moduli. The three moduli let through around one in eight candidates. Lehmer's thirty let through so few that a human could hand-check the survivors without adding much more time to the process.

  Where the candidates come from

  The first build log showed how to sieve y^2 - 2x^2 = 4001. Factoring is the same kind of problem - find whole numbers that satisfy a quadratic equation.

  Take any odd number N = p*q. Both factors are odd, so their sum and difference are even, and a = (p+q)/2 and b = (p-q)/2 are whole numbers. Then N = a^2 - b^2.  So find a and b, and the factors are a+b and a-b. So factoring can be expressed as a quadratic equation to solve in whole numbers.

  To sieve it, a starts just above sqrt(N) - about 72 million for our 16-digit number - and climbs. Our two factors turn out to be very far apart, 59,957 and 88 billion, so a reaches a solution after 44 billion. At the gear machine's 5,000 candidates a second that would be 102 days of continuous running.

  Lehmer did an additional reduction in number theory first. He showed the number must be of the form a^2 + 7b^2, and that a second solution c^2 + 7d^2 gives a factor directly as gcd(N, ad + bc). He also showed b must be a multiple of 4, so we actually solve for a^2 + 7*(4*k)^2 = N

  That leaves about 6 million candidates to check with the sieving machine.

  Here's what our console log from the RP2040 shows - we stop at the second solution for our equation after 1,471 seconds and scanning 5,676,028 numbers.

  ...
  >>> FOUND REPRESENTATION: M = 66855539^2 + 7 * 10779628^2 (k = 2694907, 706.32s) <<<
  ...
  >>> FOUND REPRESENTATION: M = 40923451^2 + 7 * 22704112^2 (k = 5676028, 1471.69s) <<<
  ============================================================
  FACTORIZATION COMPLETE in 1471.69s!
  Factors of 5283065753709209:
    Factor 1: 59957
    Factor 2: 88114244437
  Verification: 59957 * 88114244437 == 5283065753709209 (True)
  ============================================================

  Every sieve has something slower behind it

  A sieve only rejects candidates. Whatever survives has to be checked by something else, and that something else is always slower (or the sieve wouldn't be useful.)

  In 1928 the Lehmers built a sieve from 19 bicycle chains on a common shaft, one chain per modulus, with a twist of chickenwire at each accepted link tripping a microswitch, and a revolution counter for the current number. The switches were wired in series, so a candidate nobody rejected completed the circuit and stopped the motor. Then a person checked if the candidate was a solution.

  A 1932  machine built with gears replaced chains with steel gears and the switches with a beam of light through aligned holes. A photoelectric cell would detect when all holes lined up and stop the motor.

  Every number sieve ever built has the same two stages: a fast rejecter and a slower checker. New technology simply changed what each stage was made of, allowing larger and larger problems to be solved: from 60 candidates a second in 1928 to 6.4 billion in 1995, through bicycle chains, steel gears, surplus Navy delay lines and finally custom VLSI.

  Machine type	year	moduli	candidates/sec	who checks survivors
  bicycle chains	1928	19	60	human
  16mm film	~1930	18	60	human
  steel gears	1932	30	5,000	human
  delay lines	1965	36	1,000,000	printer, CDC 6400...

  Read more »

• The sound of sieving

  kbsriram • 7 days ago • 0 comments

  How would you solve an equation like 

  This isn't too hard of course, we can write

  to get all possible x, y pairs. But what if we constrain x and y to be positive whole numbers?

  Equations like this are Diophantine Equations, and are known to be hard to solve in the general case - e.g. with arbitrary powers and terms. If it has only squared terms like this (quadratic Diophantine equations) they are still known to be NP-complete, so we don't have any good way to solve them quickly either.

  Let's try to brute-force our example anyway.

  What we're looking for, are numbers of the type:

  which are themselves square numbers, since y needs to be the square root.

  Let's check for x = 1 - we get 2*1^2 + 4001 = 4003 - it's not a square number

  Let's try a few more

  x	0	1	2	3	4	5	6	7	8	9
  2x^2 + 4001	4001	4003	4009	4019	4033	4051	4073	4099	4129	4163

  You might instinctively notice that some of these numbers - e.g. - 4033 don't look like it could be a square.

  In fact, any perfect square ends in 0, 1, 4, 5, 6 or 9. The last digit (in base 10) is just arithmetic modulo 10, and so we can discard about half our numbers without going through the bother of actually calculating the square root.

  We can do the same trick with a different base - let's take everything modulo 3, and see where that gets us

  x mod 3	0	1	2
  x^2 mod 3	0	1	1
  2x^2 + 4001 mod 3	2	1	1
  could be square?	no	yes	yes

  The second row tells us only 0 and 1 can be perfect squares in mod 3 arithmetic.

  The third row tells us that 2x^2 + 4001 = 2 mod 3 when x is 0 mod 3, and the second row tells us that 2 can never be a perfect square mod 3.

  So this means any x that's 0 mod 3 can't be a solution either.

  So we can skip about a third of our brute-force check already.

  Let's do this trick for a couple more moduli

  x mod 5	0	1	2	3	4
  x^2 mod 5	0	1	4	4	1
  2x^2 + 4001 mod 5	1	3	4	4	3
  could be square?	yes	no	yes	yes	no

  mod 5 lets us avoid checking about 40% of our numbers

  x mod 7	0	1	2	3	4	5	6
  x^2 mod 7	0	1	4	2	2	4	1
  2x^2 + 4001 mod 7	4	6	5	1	1	5	6
  could be square?	yes	no	no	yes	yes	no	no

  mod 7 lets us skip checking around 60% of our numbers.

  x mod 11	0	1	2	3	4	5	6	7	8	9	10
  x^2 mod 11	0	1	4	9	5	3	3	5	9	4	1
  2x^2 + 4001 mod 11	8	10	5	4	7	3	3	7	4	5	10
  could be square?	n	n	y	y	n	y	y	n	y	y	n

  and mod 11 lets us skip about 50% of our numbers.

  We could of course keep stacking these tests. If we use prime moduli, each new  modulus removes about half the candidates, so this gets very effective very fast. If we use k moduli, only about 1/2^k candidates survive the test. (The initial few primes usually remove less than half, so in practice sieves don't bother with moduli smaller than 9.)

  The sieving mathematicians

  Imagine you have four people in a room - one per modulus. Each of them has just the last row of yes/no values for their table. So we have one person holding the mod 3 row, another holding the mod 5 row, and so on.

  A fifth person - a scorekeeper - holds a counter set at 0, and then shouts "vote".

  Everyone looks at their first cell - if it says "no" - they shout "no". If it says "yes", they keep silent. Then, they move their finger to the next cell and wait for the scorekeeper. If they get to the end of their row, they just start over.

  Most of the time, one or more people would have shouted no, and the scorekeeper just clicks their counter and shouts "vote" again.

  Every once in a while, nobody in the room would have veto'ed that number. The scorekeeper looks at their counter, and checks if it could be a solution. If not, they keep moving on.

  Let's see how this plays out in our example for the first 10 steps. Notice how the mod 3 and mod 5 rows just repeat every 3 times and 5 times respectively. Each row is just a pattern that repeats with a period equal to its modulus.

  scorekeeper	0	1	2	3	4	5	6	7	8	9	10
  the mod 3 person	N	--	--	N	--	--	N	--	--	N	--
  the mod 5 person	--	N	--	--	N	--	N	--	--	N	--
  the mod 7 person	--	N	N	--	--	N	N	--	N	N	--
  the mod 11 person	N	N	--	--	N	--	--	N	--	--	N

  At least one person vetos every number through 10, and the scorekeeper just keeps clicking...

  Read more »

View all 2 project logs