P is for Practical PerlMonks

### Comment on

 Need Help??
You're quite right, Fermat's method will only find two factors: it is important to note that all the fastest factoring algorithms (with the exception of the elliptic curve method) use this as a basis.

The Quadratic Sieve works as follows:

If n is the number to be factored, the QS tries to find x and y such that x^2 = y^2 (mod n) and x is not equal to plus or minus y; this implies that (x-y)(x+y)=0 and we compute GCD(x-y,n) to see if this is a non-trivial divisor. There is at least a 1/2 chance that the factor will be non-trivial. The first step is to define

Q(x)=(x+floor(sqrt(n)))^2-n=x'^2-n

and compute Q(x_1),Q(x_2),...,Q(x_k). Determining the x_i requires sieving over a factor base (using primes such that the Legendre symbol (n/p)=1). From the evaluations of Q(x) we want a subset Q(x_i1)Q(x_i2)...Q(x_ir) that is a square, y^2. Then note that for all x, Q(x)=x'^2 (mod n). So what we now have is that

Q(x_i1)Q(x_i2)...Q(x_ir)=(x_i1*x_i2*...*x_ir)^2 (mod n)

Which are the factors of n.

In reply to Re: Vampire Numbers by gumby
in thread Vampire Numbers by YuckFoo

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
 [Lady_Aleena]: What?! Can't stat ~/Music: No such file or directory? The ~/ doesn't expand? [Lady_Aleena]: And the env variable \$HOME doesn't work either. !@#\$ [shmem]: no, that's a shell feature. Use \$ENV{HOME} [marioroy]: my \$ans = qx{ find \\$HOME -name "*.pl" -exec ls -l {} \\; }; [marioroy]: must backslash \$ inside qx [Lady_Aleena]: I haven't written perl for a while, I've been trying to do things at the command line. I'm having to relearn a lot. [marioroy]: LA can you post the qx find again [Lady_Aleena]: Things I would have written a script for while I was on Windows, I can run simply on the command line. [Lady_Aleena]: marioroy, my @music_times = qx(find ~/Music/Albums/ -type f -iname '*.mp3' -exec mp3info -p "%S\n" {} \;); #unfixed

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (13)
As of 2017-04-23 21:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I'm a fool:

Results (432 votes). Check out past polls.