Thursday, December 15, 2011

Quadratic Sieve and others

Was procrastinating grading my exams and wandering along on wolfram Mathworld's website when I came across this sweet diagram, and a concept I had never heard of...
Start by drawing the basic parabola curve (y=x2).  Above you'll see the curve, although it's rotated to show along the x-axis instead.  Now find all the pretty points, that is, the places where the curve has nice integer coordinates, such as (1,1), (2, 4), (3, 9), (4, 16), etc, as well as (-4, 16) and so on.  If you connect all the "pretty points" with line segments, ignoring (0,0), (1,1), and (-1, 1), the line segments will all intersect the axis at "pretty" intercepts -- that is at nice integers, never at fractions or decimal locations.  Now that alone is cool...

... but if you notice from the picture, they don't intersect at ALL the pretty points.  They only intersect at specific locations, 4, 6, 8, 9, 10, 12, 14.  What's most interesting is the points that AREN'T crossed, 2, 3, 5, 7, 11, 13....  The prime numbers!  How cool is it, that if we continued this drawing forever, we would cross out all the composite numbers and leave behind all the primes.  This sifting of the numbers is why this particular scheme is called the Quadratic Sieve.

You might recall from algebra class hearing about the Sieve of Eratosthenes?  It works by going and counting by 2's and crossing every number, then counting by 3's and crossing out every number, and then 5's, and 7's, etc, until all that's left not crossed is the prime numbers.

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...