Wheel factorization: Efficient? - Page 41

CRGreathouse · 2010-08-05, 02:57

Ta.

3.14159 · 2010-08-05, 14:11

Another keyjabbed prime find: 78313127893231612361897367813698361263873441 (44 digits)

3.14159 · 2010-08-06, 13:07

Also: Random factor work: (Took about an hour)

Code:

91885725292684667767419826183883814081622727626300044377222939256039093377298088160435559401439955820110763822226867754295368572768508880923811151906822453748095935663005056815081717760000000000000001 = 137 * 6035839 * 8839801 * 249413069849 * 1622929927499 * 2621826209237 * 5343288037993 * 5409760286717 * 5488540849663 * 7579765807331 * 8958629285651 * 1635052204894562749544398018317504695557 * 672437590097057198344281325509358005935054111

kar_bon · 2010-08-06, 13:23

Quote:

Originally Posted by 3.14159

Also: Random factor work: (Took about an hour)

What type of randomness? The 200-digit number is random?

3.14159 · 2010-08-06, 13:26

Quote:

Originally Posted by kar_bon

What type of randomness? The 200-digit number is random?

It was 1 mod 70!. I also selected for some 13-digit factors to appear.

kar_bon · 2010-08-06, 13:30

Quote:

Originally Posted by 3.14159

It was 1 mod 70!. I also selected for some 13-digit factors to appear.

So you selected 13-digit-factors (7 from the 13 factors of N got 13 digits; this is almost impossible for a random number!) and build that number mod 70!?
So which number you really factored? The bigger 85-digit-part?

3.14159 · 2010-08-06, 13:33

Quote:

Originally Posted by kar_bon

So you selected 13-digit-factors (7 from the 13 factors of N got 13 digits; this is almost impossible for a random number!) and build that number mod 70!?

Modular exponentiation and PARI is your friend. See here.

Here's an example:

Code:

1352265120249817036982237029425934997648064298068519596851762859614680821727672884003698741670584760345453467431225347309566533643304563626331995745751314471759845912237782655641935371608505138533313547470492067735830755535762617413870048477974860006616971789925073344599999144035683352251778309 * d = 1 mod 160! 

d = 65777185348504634592053181479565586438282024021235225864653045387776477489871784530720951572834795190106957950707131705723580875330086509847276345158422645110406660128390041912133263437925673523052550679922718612892717693032857954485317891261443675280887760161133958532076396881264589.

Then: 1352265120249817036982237029425934997648064298068519596851762859614680821727672884003698741670584760345453467431225347309566533643304563626331995745751314471759845912237782655641935371608505138533313547470492067735830755535762617413870048477974860006616971789925073344599999144035683352251778309 * 65777185348504634592053181479565586438282024021235225864653045387776477489871784530720951572834795190106957950707131705723580875330086509847276345158422645110406660128390041912133263437925673523052550679922718612892717693032857954485317891261443675280887760161133958532076396881264589 = 88948193454990123061973788486610657405569538106272108925046671814026356784653942088753233926106507823915055028489672143154051347954633417327937011632244886976535403140436020720614191492254875527404613428753152226472443967343078605240991423446698158166583420027515895918859275047329401988423696986414508101516594103554351888525418786792335663766169401376635632560832308677724120690118161023972515305935771778819896411126345726576914453832828605739504579611258169342676407507728760674575388868136413100916870868667455930764828179092071251968000000000000000000000000000000000000001.

I selected for 13, 14, 15, and 16-digit factors. There's probably a huge cofactor that I can't factor, but you get the idea.

Quote:

Originally Posted by kar_bon

So which number you really factored? The bigger 85-digit-part?

Yep, it was the c85 cofactor.

In case you're interested, here's the cofactor:

(c194)

Code:

30059854227048536411608478310254102114633205280839469658434368659224851481064837284846942237514813945829677262352834035056544283396583848285919492364410330944245084287257882865478703558569899441

The complete incomplete factorization:

Code:

88948193454990123061973788486610657405569538106272108925046671814026356784653942088753233926106507823915055028489672143154051347954633417327937011632244886976535403140436020720614191492254875527404613428753152226472443967343078605240991423446698158166583420027515895918859275047329401988423696986414508101516594103554351888525418786792335663766169401376635632560832308677724120690118161023972515305935771778819896411126345726576914453832828605739504579611258169342676407507728760674575388868136413100916870868667455930764828179092071251968000000000000000000000000000000000000001 = 84509 * 1504563451 * 5018982229 * 154171477591 * 3798473858089 * 4720978795937 * 6039906898057 * 6969766595123 * 7357157807963 * 7910279097311 * 27302111967833 * 33130755229219 * 50079996802249 * 56201533659017 * 62258749618727 * 97948564763513 * 99031258774139 * 237867826382071 * 315223234023743 * 324357842074501 * 383687325773363 * 2415499631929547 * 2630092962410509 * 3104385748498871 * 4732532731459361 * 7455567868820767 * 141785829760950728029 * 483613060523579071201 * 30059854227048536411608478310254102114633205280839469658434368659224851481064837284846942237514813945829677262352834035056544283396583848285919492364410330944245084287257882865478703558569899441 (194 digits, composite cofactor)

Warning for guests: Pleasepleasepleasedonottryandactuallyfactorthecofactorbecauseitwilltakeyouatleast10years.Pleaseheedthiswarning.

kar_bon · 2010-08-06, 13:49

So there're 3 ways to tell this:

1. I've factored a 200-digit random number in only one hour! -> Whooo! Remarkable!!!
(like in post #443!)

2. I've factored a 200-digit random number with some 13-digit factors in it! -> Not that bad for the rest of the 200-digit number.

3. I've factored a 200-digit random number with 7 13-digit factors, remaining a 85-digit composite in only one hour! -> Yeah, such an old box I got years ago!

I've done this 200-digit "random" number in 9 minutes on my C2Q with all 4 cores already crunching for primes!

So this "random" was not random at all!
Try a second time with a really 200-digit number randomly typed! Then you see the difference!

3.14159 · 2010-08-06, 13:50

Quote:

Originally Posted by kar_bon

Try a second time with a really 200-digit number randomly typed! Then you see the difference!

Hey, you can still take the cofactor if you'd like.

I ended with a c197 cofactor for a random 200 digit number. (Update: p20 factor found)

kar_bon · 2010-08-06, 13:53

Quote:

Originally Posted by 3.14159

Hey, you can still take the cofactor if you'd like.

No thanks, I'm searching for my next 300k-digit prime.

3.14159 · 2010-08-06, 13:54

Quote:

Originally Posted by kar_bon

No thanks, I'm searching for my next 300k-digit number.

Good luck, that'll take you about 2-3 decades.

2010-08-05, 14:11	#442
3.14159 May 2010 Prime hunting commission. 2⁴·3·5·7 Posts	Another keyjabbed prime find: 78313127893231612361897367813698361263873441 (44 digits) Last fiddled with by 3.14159 on 2010-08-05 at 14:35

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Wheel Factorization	a1call	Factoring	11	2017-06-19 14:04
Efficient Test	paulunderwood	Computer Science & Computational Number Theory	5	2017-06-09 14:02
LL tests more credit-efficient than P-1?	ixfd64	Software	3	2011-02-20 16:24
A Wheel	storm5510	Puzzles	7	2010-06-25 10:29
Most efficient way to LL	hj47	Software	11	2009-01-29 00:45

2010-08-05, 02:57	#441
CRGreathouse Aug 2006 3×1,993 Posts	Ta.

2010-08-06, 13:49	#448
kar_bon Mar 2006 Germany 5534₈ Posts	So there're 3 ways to tell this: 1. I've factored a 200-digit random number in only one hour! -> Whooo! Remarkable!!! (like in post #443!) 2. I've factored a 200-digit random number with some 13-digit factors in it! -> Not that bad for the rest of the 200-digit number. 3. I've factored a 200-digit random number with 7 13-digit factors, remaining a 85-digit composite in only one hour! -> Yeah, such an old box I got years ago! I've done this 200-digit "random" number in 9 minutes on my C2Q with all 4 cores already crunching for primes! So this "random" was not random at all! Try a second time with a really 200-digit number randomly typed! Then you see the difference!