This message was too old and has been purged

[bitspill]

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]

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]

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]

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]

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]

This message was too old and has been purged

[Evil-Knievel]

This message was too old and has been purged

[pythonpro1337]

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]

This message was too old and has been purged

[Pallie]

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]

This message was too old and has been purged

[jsmit332]

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]

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]

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]

You guys are getting paid, what, ~7-8k USD, to crack ECC? Sorry, just read like 50% of this thread. Fun bounty though.

[excword]

This bounty is still running. Interesting.

[Evil-Knievel]

This message was too old and has been purged

[dothebeats]

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]

Let me try. If not work i will try again tomorrow. 


C++

Code:

#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

[Evil-Knievel]

This message was too old and has been purged