View Single Post
Old 2021-05-14, 22:36   #14
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

23×1,459 Posts
Default

(Somehow missed this when PaulU OPed it:)

Quote:
Originally Posted by paulunderwood View Post
Congrats! However:

Code:
? factor(499400852887245323683941126088449355702834653807158087 )

[       290582744822559701357207 1]

[1718618403140893608084889221841 1]
Ha! Real men (a.k.a. execrable masochists) factor numbers like this using the world's slowest bignum code - I mean of course *nix 'bc', which IIRC uses base-10 emulation of your CPU's base-2 instructions or some such ludicrously inefficient bignum implementation - and crappy bc-based functions of their own writing:

n = 499400852887245323683941126088449355702834653807158087; p = 105032111;
pm1(n,p,10^4,5*10^6,5)
Stage 1 prime-powers seed = 105032111
Stage 1 residue A = 275242671610725931867172664303887659718570581548948384, gcd(A-1,n) = 1
Stage 2 interval = [10000,5000000]:
Using base= 3; Initializing M*24 = 120 [base^(A^(b^2)) % n] buffers for Stage 2...
Stage 2 q0 = 10080, k0 = 48
At q = 209790
At q = 419790
At q = 629790
At q = 839790
At q = 1049790
At q = 1259790
At q = 1469790
At q = 1679790
At q = 1889790
At q = 2099790
At q = 2309790
At q = 2519790
At q = 2729790
At q = 2939790
At q = 3149790
At q = 3359790
At q = 3569790
At q = 3779790
At q = 3989790
At q = 4199790
At q = 4409790
At q = 4619790
At q = 4829790
Stage 2: did 23762 loop passes. Residue B = -409059575611368065569985294315721920104412510081096652, gcd(B,n) = 290582744822559701357207
This factor is a probable prime.
Processed 581936 stage 2 primes, including 234294 prime-pairs and 113348 prime-singles [80.52 % paired].


Now back to work on my cutting-edge bc-based NFS implementation, with which I hope to someday factor numbers as large as the quantum-computer folks do: "the quantum factorization of the largest number to date, 56,153, smashing the previous record of 143 that was set in 2012."

Last fiddled with by ewmayer on 2021-05-14 at 22:37
ewmayer is offline   Reply With Quote