bitspill
Legendary
Offline
Activity: 2087
Merit: 1015
|
|
February 07, 2015, 11:36:20 PM |
|
pythonpro1337: The 'p' in (mod p) is 2^255 - 19 and he's not searching for 10 but rather some arbitrarily large number such as 83402281777707715381485212681368749158073214888176003645002923212220704930559
|
|
|
|
pythonpro1337
Member
Offline
Activity: 99
Merit: 10
|
|
February 08, 2015, 02:45:45 AM |
|
pythonpro1337: The 'p' in (mod p) is 2^255 - 19 and he's not searching for 10 but rather some arbitrarily large number such as 83402281777707715381485212681368749158073214888176003645002923212220704930559
Alright, though OP did say any formula we produce should work "in all cases," which I take to mean for general p and general x. Having re-read the thread, I noticed a few things I missed earlier. Are you essentially trying to find a general method for quickly finding the discrete logarithm? Are you looking to break elliptic curve cryptography?
|
|
|
|
pythonpro1337
Member
Offline
Activity: 99
Merit: 10
|
|
February 08, 2015, 06:51:15 AM |
|
As much as I'd like to help, if I were able to find an efficient way to find the discrete logarithm, I'd publish a paper on it and hope it was enough for a Fields Medal. While a good quantum algorithm is known due to Shor, there is no known general way to find the discrete logarithm "quickly" on a classical computer. People with a lot more experience than I have (or anyone else here has) in group theory, cryptography, etc., have worked on this without success, so I wouldn't bank on getting help here.
|
|
|
|
ndnh
Legendary
Offline
Activity: 1302
Merit: 1005
New Decentralized Nuclear Hobbit
|
|
February 08, 2015, 07:08:13 AM |
|
pythonpro1337: The 'p' in (mod p) is 2^255 - 19 and he's not searching for 10 but rather some arbitrarily large number such as 83402281777707715381485212681368749158073214888176003645002923212220704930559
Alright, though OP did say any formula we produce should work "in all cases," which I take to mean for general p and general x. Having re-read the thread, I noticed a few things I missed earlier. Are you essentially trying to find a general method for quickly finding the discrete logarithm? Are you looking to break elliptic curve cryptography? Yes, I think he is looking to break ECC. I understand the issue you had, I also misinterpreted the question twice. I think I could attempt this if I had a supercomputer?
|
|
|
|
pythonpro1337
Member
Offline
Activity: 99
Merit: 10
|
|
February 08, 2015, 07:37:56 AM |
|
indeed it would require all the computers and severs powers combined all over the world to get this number, you would be talking about infecting the whole internet with a worm and telling the zombies to run this script to find the algorithm in unison statically. would be impossible but it COULD BE POSSIBLE. just saying your chances are not in any lifetimes generation soon. sorry this bounty will run till the year 3567 A.D. we just dont have the technology to solve this in any way!
CASE CLOSED!!!!
|
|
|
|
Evil-Knievel (OP)
Legendary
Offline
Activity: 1260
Merit: 1168
|
|
February 08, 2015, 08:03:32 AM Last edit: April 17, 2016, 07:56:26 PM by Evil-Knievel |
|
This message was too old and has been purged
|
|
|
|
Evil-Knievel (OP)
Legendary
Offline
Activity: 1260
Merit: 1168
|
|
February 08, 2015, 08:04:27 AM Last edit: April 17, 2016, 07:56:18 PM by Evil-Knievel |
|
This message was too old and has been purged
|
|
|
|
pythonpro1337
Member
Offline
Activity: 99
Merit: 10
|
|
February 08, 2015, 08:18:32 AM |
|
Lol, pythoncoderpro changes his messages arbitrarily. See my last quote for his original message.
so what are you trying to say? i type from computer or phone phone uses correct punctuation automatically where as im lazy when i type on the pc who cares
|
|
|
|
Evil-Knievel (OP)
Legendary
Offline
Activity: 1260
Merit: 1168
|
|
February 08, 2015, 10:45:22 AM Last edit: April 17, 2016, 07:56:12 PM by Evil-Knievel |
|
This message was too old and has been purged
|
|
|
|
Pallie
Newbie
Offline
Activity: 1
Merit: 0
|
|
February 11, 2015, 01:29:58 PM |
|
I have two questions: Is the x, for which we search the number of iterations, an integer? Does the solution have to be either a formula or a program? Because I might have one that is neither.
|
|
|
|
Evil-Knievel (OP)
Legendary
Offline
Activity: 1260
Merit: 1168
|
|
February 11, 2015, 01:32:30 PM Last edit: April 17, 2016, 07:55:00 PM by Evil-Knievel |
|
This message was too old and has been purged
|
|
|
|
jsmit332
|
|
February 12, 2015, 04:50:08 PM |
|
I have two questions: Is the x, for which we search the number of iterations an integer? Does the solution have to be either a formula or a program? Because I might have one that is neither.
It must be an integer, as we are working in the ring Z/pZ I bet it's 2
|
|
|
|
Jesse James
Newbie
Offline
Activity: 29
Merit: 0
|
|
February 13, 2015, 03:21:10 AM |
|
Though you possibly qualified it by saying "at least in the context of...", I just thought I'd note that 2 is not necessarily a generator of ℤp× where p is prime. Consider, for example, p = 7.
My bad, pythonpro1337 is correct. However, 2 is a generator of the multiplicative group of integers modulo 7237005577332262213973186563042994240857116359379907606001950938285454250989 (the order of the Curve25519 elliptic curve group), so the rest of my argument holds. Proof For convenience: N = 7237005577332262213973186563042994240857116359379907606001950938285454250989 Note that saying 2 is a generator of ℤ N× is the same as saying 2 is primitive root modulo N. Since N is prime, ϕ(N) = N-1 If 2 isn't a primitive root then then it's order must divide N-1. Given the prime factorization of N-1 = 276602624281642239937218680557139826668747 * 198211423230930754013084525763697 * 33 * 2 * 2 and the fact that: 2 (N-1)/276602624281642239937218680557139826668747 ≢ 1 (mod N) 2 (N-1)/198211423230930754013084525763697 ≢ 1 (mod N) 2 (N-1)/33 ≢ 1 (mod N) 2 (N-1)/2 ≢ 1 (mod N) We can conclude that 2 is indeed a primitive root (and thus a generator of ℤ N×).
|
|
|
|
bitspill
Legendary
Offline
Activity: 2087
Merit: 1015
|
|
February 13, 2015, 05:23:22 AM |
|
An approach idea.
Take an arbitrary x value (the one that is looked for, and find the point, that caused that value when inserted into the formula. In Mathematica that would be:
Solve[(x*x - 1)^2/(4*x*(x*x + 486662*x + 1)) == THEVALUETOLOOKFOR, Modulus -> 2^255 - 19]
Then go back the whole chain, unti you reach x=9. This can sometimes be tricky, that is why you probably have to think about it further.
Only working in the case that it's a doubled value this should find the answer without brute forcing. Disclaimer: I don't have Mathematica to test rather I'm writing based on documentation.
G = THEVALUETOLOOKFOR; _x = G; _i = 0; While[_x!=9, _x = Solve[(x*x - 1)^2/(4*x*(x*x + 486662*x + 1)) == _x, x, Modulus -> 2^255 - 19]; _i++]; Print["G (", G, ") is x=9 doubled ", _i, " times"]
|
|
|
|
Vortex20000
|
|
February 21, 2015, 12:56:42 AM |
|
You guys are getting paid, what, ~7-8k USD, to crack ECC? Sorry, just read like 50% of this thread. Fun bounty though.
|
|
|
|
excword
|
|
February 21, 2015, 02:49:30 PM |
|
This bounty is still running. Interesting.
|
|
|
|
Evil-Knievel (OP)
Legendary
Offline
Activity: 1260
Merit: 1168
|
|
February 21, 2015, 04:08:58 PM Last edit: April 17, 2016, 07:51:53 PM by Evil-Knievel |
|
This message was too old and has been purged
|
|
|
|
dothebeats
Legendary
Offline
Activity: 3766
Merit: 1354
|
|
February 22, 2015, 11:25:51 AM |
|
Reading the whole thread makes me want to learn math more and understand the different jargon laid before my own eyes. Fun bounty, Evil-Knievel. Inspired me to sharpen my mathematical skills.
|
|
|
|
larry12
|
|
February 24, 2015, 07:06:16 PM |
|
Let me try. If not work i will try again tomorrow. C++ #include<iostream.h> void main() { unsigned long int p,a,x,x0=9,num,den,i=0,flag=2015; cout<<"Input the value for the prime parameter p"<<endl; cin>>p; cout<<"Input the value for the parameter a"<<endl; cin>>a; cout<<"Input the value for the desired x"<<endl; cin>>x;
while(x0!=x) { i++; //This indicates the occurence of the i-th attempt
num=((x0*x0-1)*(x0*x0-1))%p; // num is the numerator (considered modulo p) in the formula for the new x
if((4*x0*(x0*x0+a*x0+1))%p==0) {cout<<"The desired number cannot be reached"<<endl; flag=0;} /*Modular inverse operation is defined if and only if the denominator and p are coprime; flag=0 indicates that the last message (see below) will not appear and it will make us get out of the "while"*/
else { long int A=1; while( (A*4*x0*(x0*x0+a*x0+1))%p!=1) A++; //This "while" finds the modular inverse (modilo p) of the denominator den=A; //den is the modular inverse mentioned above }
if(flag==0) break; x0=(num*den)%p; } if(flag!=0) cout<<"The desired "<<x<<" is reached through "<<i<<" iterations"<<endl; }
BTC ADDRESS : 1CeWcoy5Lv7PoZJ9JqqSsjBz7gfrLCoJpj
|
#Bitcoin The future is here.
|
|
|
Evil-Knievel (OP)
Legendary
Offline
Activity: 1260
Merit: 1168
|
|
February 24, 2015, 07:14:21 PM Last edit: April 17, 2016, 07:51:41 PM by Evil-Knievel |
|
This message was too old and has been purged
|
|
|
|
|