[數學] Prime Field 求乘法反元素

Prime Field 是以質數為模運算的 Finite Field

Prime Field 求乘法反元素

其實這是高一數學的考試範圍

可以用輾轉相除法來解

求乘法反元素是給定 x, y

求 ax = 1 (mod y) 的 a

這題目等價於給定 x, y

求 ax + by = 1 的 a

所以可以用輾轉相除法來解

舉例來說, x = 997, y = 3011

49| 997 (x)         | 3011 (y)        |3

  | 980 (-147x+49y) | 2991 (3x)       |

  +-----------------+-----------------+

 5| 17 (148x-49y)   | 20 (-3x+y)      |1

  | 15 (-755x+250y) | 17 (148x-49y)   |

  +-----------------+-----------------+

  | 2 (903x-299y)   | 3 (-151x+50y)   |1

  |                 | 2 (903x-299y)   |

  +-----------------+-----------------+

  |                 | 1 (-1054x+349y) |

a = -1054+3011 = 1957   b = 349-997 = -648

1957*997=1951129

648*3011=1951128

1957*997 - 648*3011 = 1