+ 1
POW
How can I write this code without using pow https://sololearn.com/compiler-playground/c2Nt5U7ZP9wg/?ref=app
5 odpowiedzi
+ 5
From what I see, the "go" object is trying to find n such that the modular multiplicative inverse of 1 (mod 223) is congruent to mod 223 of n*(x2-x1) - and the pow() function does it well.
To find the modular multiplicative inverse without using the pow function, you can use the Extended Euclidean Algorithm:
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
else:
d, x, y = extended_gcd(b, a % b)
return d, y, x - (a // b) * y
def modular_inverse(a, m):
d, x, y = extended_gcd(a, m)
if d != 1:
raise ValueError(f"The modular inverse does not exist for {a} (mod {m}).")
return x % m
x1 = 192
y1 = 105
x2 = 17
y2 = 56
mod_inv = modular_inverse(x2 - x1, 223)
print(mod_inv)
+ 5
Jacob Morgunov How difficult it is...🤔
And this is a child's task...😎
i=2
while(i*(x2-x1)%223!=1):
i+=1
print(i) #=79
+ 4
I'm pretty sure the easiest way is to think about what does "pow" do? How does it do it?
Once you answer those 2 questions, you should be able to write the code without it.
0
Hey