mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-10-24, 19:40   #23
dov1093
 
Oct 2021
Israel

7 Posts
Default Yes

But they compute 3^(2^p) (mode Mp) and use the verifier to check the correctnes of the computation. We suggest that - as you don't need to know the concrete result of the computation but only if it equels 9 or not - don't do the computation: just use the verifier to see if it actually equels 9 or not. As we pointed out, this will accelerate the search for prime Mp by a huge factor..
dov1093 is offline   Reply With Quote
Old 2021-10-26, 02:58   #24
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

231208 Posts
Default

If you can find a way to do that, than you are $1000000 richer (yep, that is a million bucks), as you may have just solved "P versus NP" problem (at least partially). Or deterministic solution versus a non-deterministic solution. Things work like that: you have a problem that take a while to solve (like 3-sat, or hamiltonian cycle, or factorization, or even doing a PRP test**), but once solved by a third party, i.e. a magician comes and pulls a solution out of his ass hat, then it is very easy to verify that the solution is valid (like following the logic gates' output, or the hemiltonian path, or computing the product of the factors, or verifying the PRP residue).

So, assuming we can build a magician, we won't need to do the PRP computation, but only to verify the result...

-----
** for nitpickers: mind that I didn't say that the "fac" or "prp" are np-complete

Last fiddled with by LaurV on 2021-10-26 at 02:58
LaurV is offline   Reply With Quote
Old 2021-10-26, 03:30   #25
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

10111000111102 Posts
Default

Quote:
Originally Posted by dov1093 View Post
This is done without comuting 3^(2^p) (mode Mp)!
How do you propose to run Pietrzak's verification, which employs 2v values of size p bits each, generated and saved along the way of computing 3^(2^p) (modulo Mp), where v is the verification proof power, without computing those values by computing 3^(2^p) (modulo Mp)? Or put another way, how do you propose to defeat the verifiable delay function? How do you propose to compute the verification function without its required inputs?
kriesel is online now   Reply With Quote
Old 2021-10-26, 04:23   #26
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2·23·137 Posts
Default

This is just the information time-travel ontology paradox thing, right?

You take some information back in time and give to someone to invent some new (for that time) thing. Then after time passes and you are born and things, you take the information back in time "again" to complete the loop. And, magically, anti-gravity tech now exists.

But where does the original information come from initially?

You can't verify a proof if the proof doesn't exist yet. I'll leave it to you to wait for a time traveller from the future to pass you the proof files to verify.
retina is offline   Reply With Quote
Old 2021-10-26, 05:45   #27
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24×613 Posts
Default

Quote:
Originally Posted by retina View Post
But where does the original information come from initially?
What do you mean? From the magic hat. Didn't I tell you?
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Stupid question reloaded LaurV Information & Answers 14 2015-06-18 23:37
There is -no- such thing as a stupid question? Uncwilly Lounge 19 2013-03-07 04:44
Possibly stupid question about PRP. Biggles Prime Sierpinski Project 3 2006-02-07 22:50
probably a stupid newbie question... rpropper GMP-ECM 15 2005-11-14 14:43
Stupid Question fropones Math 2 2003-05-28 00:44

All times are UTC. The time now is 15:39.


Tue Nov 30 15:39:40 UTC 2021 up 130 days, 10:08, 0 users, load averages: 2.06, 1.84, 1.67

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.