Prev: portrait of infinity in Old Math #687 Correcting Math
Next: What is the difference between a value judgment and a fact (descriptionvs prescription)
From: Steve Mayer on 21 Jul 2010 07:42
You can find the inverse of p (mod q) a lot faster than that
(especially if you don't know phi(q) or the factorization
of q) by (extended) Euclid's algorithm.

GM
*****************************************************
Okay, I read chapter 3 in Rosen's book "Number Theory and its Applications" and now I see what you mean about finding the inverse. It takes O[(log q)^3]if you use the Euclidean algorithm, and factoring q is much slower than that.

Thanks again,

Steve
First  |  Prev  | 
Pages: 1 2
Prev: portrait of infinity in Old Math #687 Correcting Math
Next: What is the difference between a value judgment and a fact (descriptionvs prescription)