Register FAQ Search Today's Posts Mark Forums Read

 2019-07-30, 04:50 #1 JuanTutors     "Juan Tutors" Mar 2004 24×5×7 Posts About LL test cycles I assume we know that we can test for LL test cycles pretty easily. Instead of checking for repeated residue, we can store the units digit of the residue after each cycle in ram or on hard drive, and periodically check for repeating digits in this string in less than 1 second, and then verifying a true cycle exists by running a number of steps equal to the cycle length. Is the reason we don't do that that the probability is so low from what we can tell?
2019-07-30, 05:17   #2
axn

Jun 2003

34·5·13 Posts

Quote:
 Originally Posted by dominicanpapi82 Is the reason we don't do that that the probability is so low from what we can tell?
Yep. Totally pointless.

2019-07-30, 15:39   #3
JuanTutors

"Juan Tutors"
Mar 2004

24×5×7 Posts

Quote:
 Originally Posted by axn Yep. Totally pointless.
Thanks! Also, I can hear the bunny's head hit the ground in your avatar. Reminds me of that gif of the utility pole jumping ropes with power lines.

2019-07-30, 23:12   #4
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

3·19·107 Posts

Quote:
 Originally Posted by dominicanpapi82 I assume we know that we can test for LL test cycles pretty easily. Instead of checking for repeated residue, we can store the units digit of the residue after each cycle in ram or on hard drive, and periodically check for repeating digits in this string in less than 1 second, and then verifying a true cycle exists by running a number of steps equal to the cycle length. Is the reason we don't do that that the probability is so low from what we can tell?
How big is this units digit you mention; the rightmost 1 bit? 4 bits? 64 bits?
See https://www.mersenneforum.org/showpo...1&postcount=10

2019-07-31, 03:58   #5
JuanTutors

"Juan Tutors"
Mar 2004

24·5·7 Posts

Quote:
 Originally Posted by kriesel How big is this units digit you mention; the rightmost 1 bit? 4 bits? 64 bits? See https://www.mersenneforum.org/showpo...1&postcount=10
I just mean the last bit, stored locally. For an n-digit mersennes, the file would be n bits large, and does not need to be uploaded. Quick math says the probability of a cycle existing is approximately p/Mp if the residues are distributed randomly within the range [0,Mp-1]. I'm not saying that number isn't exceedingly small if the residues are in fact randomly distributed. My question is partially asking whether the question about cycles existing is open, and partially about whether the cost is close to zero enough that it's interesting to try to answer.

2019-07-31, 04:27   #6
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

23×32×137 Posts

Quote:
 Originally Posted by dominicanpapi82 in less than 1 second
Do you mean like 330 times slower than the LL test itself is done?
(Think about the fact that each iteration takes, say, 3 milliseconds, in an average processor, for an average exponent.)

Joking apart, and from mathematical point of view, the length of a cycle would be closely related to the znorder of the factors. And smallest factors are larger than the exponent, by at least a factor of 2 (for p=4k+3) or 6 (for p=4k+1). If m turns out prime, there are no cycles (beside of the trivial 2-2-2-2-2). For composites, possible cycles are larger than the number of iterations we do. We'll never find one... (even the trivial cycle for a prime, happens AFTER the test is finished)

Last fiddled with by LaurV on 2019-07-31 at 04:36

2019-07-31, 04:39   #7
JuanTutors

"Juan Tutors"
Mar 2004

24×5×7 Posts

Quote:
 Originally Posted by LaurV Do you mean like 330 times slower than the LL test itself is done? (Think about the fact that each iteration takes, say, 3 milliseconds, in an average processor, for an average exponent.)
True! Perhaps much faster than that. And looking for a cycle is probably significantly faster than looking for other things. Nearly free, except for the fact that the string has to be stored, so it does take SOME memory and circles per iteration. Really depends on how useful or interesting the question is. I would estimate that it would add perhaps a minute per LL test based on absolutely nothing.

 Similar Threads Thread Thread Starter Forum Replies Last Post cardmaker Factoring 4 2016-12-29 15:52 Unregistered Information & Answers 7 2013-02-16 02:24 Sleepy Msieve 18 2011-06-10 09:16 T.Rex Math 1 2010-01-03 11:34 Unregistered Information & Answers 0 2007-07-19 12:24

All times are UTC. The time now is 08:54.

Thu Jan 20 08:54:13 UTC 2022 up 181 days, 3:23, 0 users, load averages: 1.60, 1.82, 1.64