20191025, 19:48  #1 
"Michael"
Aug 2006
Usually at home
2×41 Posts 
Calculating inverses quickly.
Do you think this would be faster than the extended Euclidean Algorithm for finding inverses?
For a given a find a^{1} (mod m) 1. Let m = r mod a 2. Find r^{ 1} mod a 3. Let x = a  r^{ 1} (ie, x = r^{ 1} mod a) 4. a^{1} mod m = (xm + 1)/a If this algorithm is applied recursively, at step 2., it should be possible to reduce the question finding the inverse of a small number and then working back up the chain to find the original inverse. The reasoning is as follows: aa^{1} = km + 1, for some k < a, so km = 1 (mod a) That is, k = m^{ 1} (mod a) Adding 1, km + 1 = 0 (mod a) Whence, (km + 1)/a = a^{1} (Moderator, I meant to post this in the computing forum but posted here by mistake.) Last fiddled with by mgb on 20191025 at 20:45 
20191026, 13:48  #2  
Feb 2017
Nowhere
2·2,687 Posts 
Quote:
Last fiddled with by Dr Sardonicus on 20191026 at 13:51 Reason: Rephrasing 

20191026, 19:21  #3  
"Michael"
Aug 2006
Usually at home
2×41 Posts 
Quote:
Example: Find 17^{ 1 } mod 223 223^{ 1 } = 8 mod 17 (8*223 + 1)/17 = 105 = 17^{ 1 } mod 223 Last fiddled with by mgb on 20191026 at 19:41 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Padic inverses  devarajkandadai  Number Theory Discussion Group  1  20181110 05:17 
calculating with circles  diep  Homework Help  9  20140712 12:14 
Calculating E based on B1  c10ck3r  Math  1  20120222 06:29 
Calculating a difficult sum  CRGreathouse  Math  3  20090825 14:11 
Can I quickly unreserve & get my assignments back?  petrw1  PrimeNet  18  20081115 23:51 