aajjbb's blog

Problem on Modular Inverse
By aajjbb, 9 years ago, In English

Hello,

I recently solved problem RSA. But one detail confused me. One of the needs of the problem is to find the modular inverse of one number A module MOD. I always computed this operation with Euler's theorem stated here Theorem. But in this problem, surprisingly, it doesn't work, and I had to compute this modular inverse though the Extended GCD algorithm. Is there any cases which Euler's theorem doesn't work ?

Euler's theorem Code (I've used this code in dozens of problems without trouble)

Extended GCD Code

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

m - 2 = φ(m) - 1 when m is prime and in this problem it is definitely composite.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Euler's theorem works fine for prime numbers, but afaik Mod in rsa encrypting is not a prime one.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Actually it works for composite numbers too. The only thing you must keep in mind — a and m must be coprime.
    The problem here is in calculation of Euler's function of a composite number.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So, for non coprime numbers, only the extended gcd algorithm works ?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        For non-coprime integers there is no modular inverse number.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But the problem states that A and B are coprime, then, my curiosity is why I have different results using Fermat's Little Theorem and Extended GCD algorithm ?

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            One more time: because Fermat's Little Theorem works only for prime modulo. For composite modulo use the general case — the Euler's theorem.

            → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I believe you say about Fermat's little theorem which is particular case of Euler's theorem.

    → Reply