Hey everyone,
I came across something pretty wild that I thought was impossible, but turns out it actually is possible.
We can figure out if one number is divisible by another under modulo N without any prior knowledge, and by that I mean just using basic operations like addition, subtraction, multiplication, and division, plus direct comparisons (you know, +, -, *, / ==).
This opens up the door to tackle the ECDLP under modulo N, but it raises the question of how we can apply this method under modulo P. It works with any number, but how does it translate to curves?
Here's a quick example of how to check if a number is divisible by 123456 using Python:
* EDIT * Just a note, the int() function here is to convert from float (like 123.0) back to an integer (123), and you'll see the divisible results end with .0.
N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
N2 = 78074008874160198520644763525212887401909906723592317393988542598630163514318
Z = 55539364884045311247562660492089512137756313339020479813129993372185873536791
P1 = 123456*123
R1 = (P1*N2 % N)
D = int(P1/123456)
R2 = (R1-(Z*D) % N)
if R2 == 0:
print("Divisible by 123456!")
else:
print("Not divisible by 123456!")
Explain your code:
What is the target?
Should it always be 123456?
What are N2 and Z?
Use the function
Regards!
edit:
tested, in ecc your code always results in infinity, whether divisible or not.
Your divisions are standard divisions (using "/") which is incorrect, hence your confusion, in mod N to divide the dividend is multiplied by the modular inverse of the divisor.
the correct form would be:
Indeed, true what you said, if we use modular inverse multiplication instead of normal division it doesn't work (I mean, it works for all points, hence it doesn't detect it = isn't useful):
code example:
N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
N2 = 78074008874160198520644763525212887401909906723592317393988542598630163514318
Z = 55539364884045311247562660492089512137756313339020479813129993372185873536791
def modInv(a, m):
return pow(a, -1, m)
P1 = 123456*123
R1 = (P1*N2 % N)
D = P1 * modInv(123456, N)
R2 = (R1-(Z*D) % N)
if R2 == 0:
print("Divisible by 123456!")
else:
print("Not divisible by 123456!")
I dont understand what is Z and N2
but, if you looking for how to use this on point, see, you czn calc what is a point = 0, or 2 for ex, and then replace numbers in you code to points coordinates, to points coordinates, identify good result easy.So, if you know how to take this point (R2/ you can crack 2**130 in 65 times divides by 2.
if R2 == 0
edit, your code not work:
Divisible by 123456!: 1 2 9999999 etc