mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-12-07, 20:16   #23
MS63
 
Oct 2005

22·32 Posts
Default

Thank you to those of you who have proferred a little support. Most of all my thanks go to John Renze whose reply to my question was first, best, and provided a full answer.

RD - You are not my teacher. I am not your pupil. I pity anyone ever put in that position.

You may be blessed with the most profound mathematical knowledge and detailed insight into how LL testing works but that does not give you the right to preach at and try to belittle those of us who do not.

I have made a point of reading some of your posts in other threads. Your attitude is appalling and your arrogance despicable. I will never, in future, read anything you have posted on any thread.
MS63 is offline   Reply With Quote
Old 2005-12-07, 20:51   #24
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by MS63
Thank you to those of you who have proferred a little support. Most of all my thanks go to John Renze whose reply to my question was first, best, and provided a full answer.

RD - You are not my teacher. I am not your pupil. I pity anyone ever put in that position.

You may be blessed with the most profound mathematical knowledge and detailed insight into how LL testing works but that does not give you the right to preach at and try to belittle those of us who do not.

I have made a point of reading some of your posts in other threads. Your attitude is appalling and your arrogance despicable. I will never, in future, read anything you have posted on any thread.

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-12-07, 21:01   #25
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-12-08, 08:53   #26
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

37·281 Posts
Default

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
xilman is online now   Reply With Quote
Old 2005-12-08, 11:42   #27
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-12-08, 12:36   #28
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

37·281 Posts
Default

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
xilman is online now   Reply With Quote
Old 2005-12-08, 14:00   #29
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-12-08, 15:13   #30
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

289D16 Posts
Default

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
xilman is online now   Reply With Quote
Old 2005-12-08, 15:28   #31
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-12-10, 00:11   #32
ppo
 
ppo's Avatar
 
Aug 2004
italy

113 Posts
Default

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?
ppo is offline   Reply With Quote
Old 2005-12-10, 13:09   #33
MS63
 
Oct 2005

22·32 Posts
Default

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.
MS63 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
SIGSEGV in xi3eK8 running torture test GordonWade Information & Answers 10 2018-02-18 00:07
Can I just start Prime95 by running torture test? marks9GIMPS Information & Answers 5 2011-06-05 18:44
Dual Core and running the same test..? Unregistered Information & Answers 1 2008-03-01 15:02
Prime95 crashing while running blend test day61 Hardware 1 2007-01-30 12:03
Running a LL test on 2 different machines 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.