(a/b) mod p ?

bhelmes · 2020-11-13, 21:40

What is the fastest way to calculate a rational number a/b with a, b element N and gcd (b,p)=1 mod p where the result is in N ?

Nick · 2020-11-13, 21:44

Quote:

Originally Posted by bhelmes

What is the fastest way to calculate a rational number a/b with a, b element N and gcd (b,p)=1 mod p where the result is in N ?

Is the Euclidean algorithm not fast enough for you?

2020-11-13, 21:40	#1
bhelmes Mar 2016 2³×37 Posts	(a/b) mod p ? What is the fastest way to calculate a rational number a/b with a, b element N and gcd (b,p)=1 mod p where the result is in N ?