mersenneforum.org > Math Running LL test from both ends of the sequence?
 Register FAQ Search Today's Posts Mark Forums Read

2005-12-07, 20:51   #24
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:

Once you come into this forum, professing ignorance, you become a student.
I find your attitude appalling. You failed to do even basic required reading.

The problem with American education today is that teachers are ALLOWING
students to be lazy. They are ALLOWING students to be unprepared.
The result is the "dumbing down" of America.

My knowledge of the subject DOES give me the right to preach and prattle
to someone who asks questions in ignorance.

I find *your* attitude to be worthy of total contempt. If you are not willing
to do necessary preparation for class, then you have no business in class.
When you come here, professing ignorance, this becomes a classroom.
If you are not interested in learning, then LEAVE.

For my part, I have put YOU into the category of "asks questions when
unprepared, therefore is not worth replying to".

So let us just leave it as mutual disdain.

2005-12-07, 21:01   #25
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by alpertron We can assume "a priori" that the number is prime. If we cannot compute the square root, the Mersenne number must be composite,
A difficulty (one of many) is that you may not know that you have failed to
correctly compute a square root. Suppose the candidate is 3 mod 4.
A simple [but extremely expensive] calculation gives a "square root", but
the answer will be wrong if the candidate isn't prime. {i.e compute
a^(n+1)/4 mod n}. Furthermore, computation of the square root is as
expensive as an entire L-L test itself!

The entire idea is pointless.

2005-12-08, 08:53   #26
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

37·281 Posts

Quote:
 Originally Posted by R.D. Silverman A difficulty (one of many) is that you may not know that you have failed to correctly compute a square root. Suppose the candidate is 3 mod 4. A simple [but extremely expensive] calculation gives a "square root", but the answer will be wrong if the candidate isn't prime. {i.e compute a^(n+1)/4 mod n}. Furthermore, computation of the square root is as expensive as an entire L-L test itself! The entire idea is pointless.
However, testing validity of a supposed square root is as easy as validating a supposed factorization. It's precisely the same operation: multiplication.

I really think we need to separate out the two threads of this discussion. Whether it is possible to "meet in the middle" and whether it is cost-effective to do so.

As has been pointed out, it is possible. Make the working assumption that the final LL residue is zero and extract square roots. If you fail to find a square root or if the central values don''t match you have a proof of compositeness.

As also pointed out, it is not cost-effective. Extracting square roots is much more expensive than squaring.

Can we put this one to bed now?

Paul

2005-12-08, 11:42   #27
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by xilman However, testing validity of a supposed square root is as easy as validating a supposed factorization. It's precisely the same operation: multiplication. I really think we need to separate out the two threads of this discussion. Whether it is possible to "meet in the middle" and whether it is cost-effective to do so. As has been pointed out, it is possible. Make the working assumption that the final LL residue is zero and extract square roots. If you fail to find a square root or if the central values don''t match you have a proof of compositeness. As also pointed out, it is not cost-effective. Extracting square roots is much more expensive than squaring. Can we put this one to bed now? Paul
No, it isn't even possible. One would need to maintain an exponentially
sized tree of square roots. Storage would be insufficient.

2005-12-08, 12:36   #28
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

37·281 Posts

Quote:
 Originally Posted by R.D. Silverman No, it isn't even possible. One would need to maintain an exponentially sized tree of square roots. Storage would be insufficient.
Once more, you are conflating possibility with cost-effectiveness.

We are in complete agreement that an inconveniently large amount of storage would be required to store the intermediate values for all but the very tiniest problems and so it would not be cost-effective. Nonetheless, it could be done in principle, given an open universe and a sufficiently compact encoding method.

Let me choose another example. One could, in principle, factor a kilobit RSA public modulus by trial division, if you had enough sufficiently fast machines and were prepared to wait long enough. Compared with NFS, or even QS, it would not be cost-effective.

On the other hand, there are problems which can not be solved computationally, no matter how many resources are thrown at them and no matter how long they are employed. You gave an example of one on the forum not long ago: computing a real number alpha which can be used to generate the sequence prime numbers. Alpha exists but is not computable, even in principle, with finite resources. Performing a reverse LL test on a specific Mersenne number requires only finite resources, though excessively large.

Perhaps you're really an engineer at heart and not a mathematician

Paul

2005-12-08, 14:00   #29
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by xilman Once more, you are conflating possibility with cost-effectiveness. We are in complete agreement that an inconveniently large amount of storage would be required to store the intermediate values for all but the very tiniest problems and so it would not be cost-effective. Nonetheless, it could be done in principle, given an open universe and a sufficiently compact encoding method. Let me choose another example. One could, in principle, factor a kilobit RSA public modulus by trial division, if you had enough sufficiently fast machines and were prepared to wait long enough. Compared with NFS, or even QS, it would not be cost-effective. On the other hand, there are problems which can not be solved computationally, no matter how many resources are thrown at them and no matter how long they are employed. You gave an example of one on the forum not long ago: computing a real number alpha which can be used to generate the sequence prime numbers. Alpha exists but is not computable, even in principle, with finite resources. Performing a reverse LL test on a specific Mersenne number requires only finite resources, though excessively large. Perhaps you're really an engineer at heart and not a mathematician Paul
No, I am not. The universe isn't big enough, even at Planck scale
lengths to hold the tree.

2005-12-08, 15:13   #30
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

289D16 Posts

Quote:
 Originally Posted by R.D. Silverman No, I am not. The universe isn't big enough, even at Planck scale lengths to hold the tree.
To hold which tree?

Are you denying that we could test M11 by squareroot extraction?

The Planck scale is approximately 1e-35 metres. The observable universe is around 1e27m across, or about 1e62 Planck lengths. As time goes by, the observable universe becomes larger but let's ignore that for the moment. In three dimensions, we have about 1e186 storage elements if we can find a way of encoding information in spacetime quanta. 1e186 is approximately 2^620 --- so we could presumably test up to M1201 or so in the spacetime we can see right now. However, earlier I expressed a desire that the universe be open ...

I concede that solving the engineering problems would be decidedly non-trivial.

Paul

 2005-12-08, 15:28 #31 akruppa     "Nancy" Aug 2002 Alexandria 1001101000112 Posts We would not need to store the tree, either. Do the forward half of the test, then look for the residue in the tree by traversing it, examining one node at a time. We only need storage equal to the depth of the tree this way. Not that this makes any difference regarding the practicality of the idea... but hey, while we're splitting hairs we might as well split them the whole length. Alex
 2005-12-10, 00:11 #32 ppo     Aug 2004 italy 113 Posts I understand that the all exercise is pointless, but I am curious, and this is probably my opportunity to be jumped on by Bob, or by all of you, for 1) being ignorant 2) not having done my homework 3) being lazy 4) asking stupid questions but I am still unable to work backward starting from 0. Would some kind soul walk me through an example with a very small exponent?
2005-12-10, 13:09   #33
MS63

Oct 2005

22·32 Posts

Quote:
 Originally Posted by ppo I understand that the all exercise is pointless, but I am curious, and this is probably my opportunity to be jumped on by Bob, or by all of you, for 1) being ignorant 2) not having done my homework 3) being lazy 4) asking stupid questions but I am still unable to work backward starting from 0. Would some kind soul walk me through an example with a very small exponent?
Oh simple, foolish one.

One would have thought that a forum such as this was exactly the place to ask ANY questions and be provided with a RELEVANT answer, but no: According to 'Lord Bob' 1) is not permitted, 2) is mandatory, 3) is tantamount to a criminal offence, 4) is outlawed, and all are reasons to NOT ask one's question. One should NEVER ask a question unless one already knows the answer.

Seems to make this forum entirely pointless.

 Similar Threads Thread Thread Starter Forum Replies Last Post GordonWade Information & Answers 10 2018-02-18 00:07 marks9GIMPS Information & Answers 5 2011-06-05 18:44 Unregistered Information & Answers 1 2008-03-01 15:02 day61 Hardware 1 2007-01-30 12:03 lycorn Software 10 2003-01-13 19:34

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

Sat Dec 5 08:53:41 UTC 2020 up 2 days, 5:05, 0 users, load averages: 1.24, 1.17, 1.37