Talk:Modular multiplicative inverse

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Mid Importance
 Field: Number theory

Modified the New examples to show why the repeating numbers terminated the computation
the old explanation is here, which doesn't explain why we terminate
the old examples also use inconsistent notation for the repeating case

assume we want to get x-1 we can do this as following.
x-1 = x * x-2
x-2 = x2 * x-4

we continue this expansion until it terminates with either a repeated number, or a one.
NeilUK 20:30, 20 June 2007 (UTC)

New Modular Multiplicative Inverse Algorithm[edit]

I'm going to remove this algorithm, because it is badly described and significantly slower than the extended Euclidean algorithm and the modular exponentiation method (even if we have to factor the modulus first). Furthermore it appears to be original research. 08:21, 17 July 2007 (UTC)

PHP Script[edit]

I think it should be better to use pseudo-code or a more general-purpose language, like C. Squalho (talk) 16:55, 30 January 2009 (UTC)

I'm in complete agreement. The PHP script is absolutely unreadable and seemingly useless. I will work on rewriting. (talk) 20:47, 7 February 2009 (UTC)

Newton's method[edit]

According to Hacker's Delight Newton's algorithm, , apparently also works in modular arithmetic, for powers-of-two anyway. Perhaps this ought to be mentioned?

At very least this results in a short and sweet (not to mention efficient) implementation if one is needed for the article.

unsigned int modinv(unsigned int d) {
	unsigned int t, x = d;
	do {
		t = 2 - d*x;
		x *= t;
	} while(t != 1);
	return x;

-- (talk) 23:02, 29 April 2009 (UTC)

Perhaps there should be a mention of negative values for the Modular multiplicative inverse?[edit]

Correct me if I'm wrong but doesn't the fact that the solution of Bezout's Identity ax + by = 1 require that either x or y to be negative? If so then this means that its Modular multiplicative inverse is not 1 but - (a - 1) or - (b - 1). Perhaps a small mention of this might be helpful? —Preceding unsigned comment added by (talk) 07:37, 19 March 2010 (UTC)

If a is the modulus then the product of the number to invert and its inverse is -(a - 1) which is equal to -a + 1. However -a + 1 = 1 (mod a). Basically, you forgot we're working over a modulus. —Preceding unsigned comment added by Mindvirus (talkcontribs) 21:21, 5 May 2010 (UTC)

I think the last line "return x % m" should read "return (x+m) % m", since in most common programming languages, a modulus of a negative number is negative. --Erel Segal (talk) 14:37, 7 November 2010 (UTC)
Not in Python. -- X7q (talk) 15:52, 7 November 2010 (UTC)

Fermat's little theorem algorithm[edit]

I am removing this. It is a specific case of direct modular exponentiation by Euler's theorem, already described. —Preceding unsigned comment added by (talk) 21:08, 5 May 2010 (UTC)

What kind of notation is this?[edit]


The article can be improved by explaining where this notation

      (Equation 1)

comes from? It's supremely horrible and confusing.

Consider this: by looking at this we learn that

                  (Equation 2)

then there exists an integer k, such that

                  (Equation 3)

So now comparing the first two equations we see that

                                    (Equation 4)

which means that Equation 1 can be converted to the form of Equation 3:

      in other words                   (Equation 5)

Thus by following standard notation, I have shown that if Equation 1 is true, then Equation 5 must also be true (one can find an integer k such that Equation 5 is true). But of course it is not, since the left-hand side of Equation 5 cannot be an integer (if e.g. a = 5).

So my question: where the hell does the notation used in Equation 1 come from? This definitely needs to be improved in the article, because currently it's just confusing. I'd like to know: who first used that notation? What's its history? Are there any other notations?
Because I'd never use Equation 1, but instead write:

      (Equation 6)

Math;singular (talk) 20:02, 18 January 2011 (UTC)

What the heck!??[edit]

Can someone explain this to me?

I can't get it to turn out the way I'm expecting...

From RSA:

  1. Choose two distinct prime numbers, such as: and . I get this.
  2. Compute giving: n = 61 · 53 = 3233. I get this.
  3. Compute the totient of the product as giving: . I get this.
  4. Choose any number that is coprime to 3120. Choosing a prime number for leaves us only to check that is not a divisor of 3120. Let . I get this.
  5. Compute , the modular multiplicative inverse of yielding: . HALP! I don't get this!

I get everything up until "modular multiplicative inverse".

d obviously does not equal 1 / (17 mod 3120), so... What am I missing here? – Ajltalk 07:40, 25 March 2011 (UTC)

Gandalf61 (talk) 15:18, 25 March 2011 (UTC)
I must be a complete idiot then, because that still makes no sense at all. I don't know what is! I only know what it is because someone told me (the RSA article). I guess I should have worded my question better: How do you find the value of ?Ajltalk 15:31, 25 March 2011 (UTC)
Well, you can use trial and error - you know d has to be less than 3120, so there are a limited number of possibilities. Or you can use the extended Euclidean algorithm, which goes something like this:
Gandalf61 (talk) 09:42, 26 March 2011 (UTC)

Efficiency of exponentiation under Euler's theorem[edit]

I updated the Euler's theorem section to say

  • exponentiation. Though it can be implemented more efficiently using modular exponentiation, an efficient implementation of this operation itself requires the calculation of an inverse mod m in the first place (...)

This was to clarify a previous edit which had been reverted by User:X7q

A read of the modular exponentiation article confirms that the efficient method for modular exponentiation, namely the Montgomery method, does use a multiplicative inverse. Since this section is about the efficiency of the Euler method to calculate the inverse, I believe it is justified to use the most efficient method as the basis for the discussion. But maybe there's an even better way to explain it, I'm certainly open to discuss it.

Even if it isn't, the page before my updates did contain a mistake which I corrected (it said that modular exponentiation is a form of binary exponentiation, which is clearly not true since binary exponentiation is simply one of the methods that can be used to calculate an exponent). (talk) 11:33, 10 July 2011 (UTC)

Modular exponentiation can be efficiently performed using binary exponentiation algorithm, which doesn't require modular inverses. So I still think that your edit is wrong. -- X7q (talk) 11:38, 10 July 2011 (UTC)
Binary exponentiation without Montgomery multiplication is certainly not efficient when big numbers are involved. It requires a lengthy division at every step in order to reduce the intermediate results mod m. With the Montgomery method the only divisions required are by powers of 2 which are very efficient on any binary computer (and it can be adapted to other bases too I believe). (talk) 11:44, 10 July 2011 (UTC)
Your edit made it sound like modular inversion is a required operation in modular exponention, which it isn't. Multiplication can be done without Montgomery reductions just fine, although, yes, it could be slower. -- X7q (talk) 12:01, 10 July 2011 (UTC)
It's required for efficiency when a big value of m is involved. But I definitely see your point, so I think the best solution would be to update the page to say this objection applies for big values of m (which is when Montgomery reduction becomes the efficient solution, and normal binary exponentiation is inefficient). Do you agree or do you have another idea? (talk) 12:04, 10 July 2011 (UTC)
Agree. Please mention that implementations of modular exponentiation for large moduli typically use Montgomery reductions for efficiency, and that Montgomery reductions can not be used in this case because they require modular inverses. -- X7q (talk) 12:09, 10 July 2011 (UTC)
Done. I think the page is definitely better after our discussion, but I'm sure my phrasing is not optimal so feel free to improve it if needed. Thanks for the discussion! (talk) 12:27, 10 July 2011 (UTC)
I agree, it looks much better now. Thank you! -- X7q (talk) 12:37, 10 July 2011 (UTC)

Why remove?[edit]

  • Example.
— Preceding unsigned comment added by Versatranitsonlywaytofly (talkcontribs) 21:38, 11 March 2012 (UTC)
There is already an example in the article, much simpler, with smaller numbers and more understandable. I don't think we need another one. It doesn't illustrate anything. -- X7q (talk) 21:52, 11 March 2012 (UTC)
BTW, does anybody know how to find x? It seems pretty hard. — Preceding unsigned comment added by Versatranitsonlywaytofly (talkcontribs) 21:40, 11 March 2012 (UTC)
The Computation section describes two methods. -- X7q (talk) 21:52, 11 March 2012 (UTC)
OK, I get it,
— Preceding unsigned comment added by Versatranitsonlywaytofly (talkcontribs) 22:13, 11 March 2012 (UTC)
On scientific MS Windows calculator need push first "3120", then "Mod", then "17" and you get result "9". So does it correct to write ? Maybe need to write ? — Preceding unsigned comment added by Versatranitsonlywaytofly (talkcontribs) 22:33, 11 March 2012 (UTC)
is a false statement. is a true statement. -- X7q (talk) 22:43, 11 March 2012 (UTC)
Then need rewrite all "MODed" wikipedia, because here also as you claiming . In this papper even written 7^123 Mod 19 = 1 as a=7 and a^123 = 1 (mod 19). Or also 1 = 11^123 Mod 19 as So it written as anybody likes. I think after all, that on calculator you must first enter 3120, then 17, then you get 9, but to write you obviously need because thats how written MOD wikipedia article.
Nobody needs to rewrite anything. is a standard (i.e. textbook) math notation, with a simple and very precise meaning: a - b is divisible by m. Nothing else. Like it or not, that's how math is written, deal with it. Let me guess, you probably also wouldn't like how integrals are written, and be shocked discover that dy/dx isn't in fact a fraction :) -- X7q (talk) 09:53, 6 April 2012 (UTC)
Regarding 7^123 Mod 19 = 1 - in this example it appears that "Mod" denotes the operation of taking a remainder. Not very widespread notation, but I've seen it. Note that it isn't the same as the other notation. For example 7^123 Mod 19 = 20 is false (left hand side evaluates to 1, but RHS is 20). While denotes the fact that is divisible by 19, and is a true statement. -- X7q (talk) 09:59, 6 April 2012 (UTC)
If you are confused by the notation, you definitely should read a more basic Modular arithmetic article first. -- X7q (talk) 22:47, 11 March 2012 (UTC)

Please do not delete anything (even junk) from talk pages[edit] — Preceding unsigned comment added by (talk) 19:33, 8 April 2012 (UTC)

Example wording[edit]

First its stated that "and there are no other values of x in \mathbb{Z}_{11} that satisfy this congruence" then, a line later, "Once we have found the inverse of 3 in \mathbb{Z}_{11}, we can find other values of x in \mathbb{Z} that also satisfy the congruence". Isn't that contradictory? — Preceding unsigned comment added by (talk) 13:48, 28 October 2012 (UTC)

is the finite group consisting of the 11 equivalence classes of integers modulo 11. Of these 11 equivalence classes, only one satisfies the equation , and that is the equivalence class that contains 4. In the set of integers , this equivalence class corresponds to the infinite set of integers that are congruent to 4 mod 11 i.e. ..., -18, -7, 4, 15, 26, ... So there is no contradiction - the context for the two statements is just different. Gandalf61 (talk) 09:13, 29 October 2012 (UTC)

Messy and terribly frustrating article[edit]

The example and computation sections just make the whole concept impossible to understand: 1) What the heck is the "=" sign with 3 bars? 2) What is Z(11)? 3) Why are these equations bitmaps instead of Unicode text? 4) Why don't any of these have a wikipedia hyperlink? 5) Most visitors land in this page because of the RSA article. Why is there no detailed example for 17 (mod 3120)? I tried other numbers than 17 and 3120, to no avail. Searched the whole web, not a single understandable example either.

Explanation of mathematical notation is missing - making the whole article almost useless[edit]

The article starts with a term, which has the three-horizontal-lines mathematical sign, which is probably not known to a majority of people, ever to bump into this article. If a reader is familiar with this notation and principles, why would they ever ask Wikipedia? Sorry, Wikipedia is not a encyclopedia for people who already know everything, but for people curious finding out new things. If someone could make this article better? Reference to other existing articles regarding the notation might also be very useful for the beginning. Thank You! — Preceding unsigned comment added by (talk) 12:15, 10 February 2014 (UTC)

why not even more complicated ? not a good article [sarcasm][edit]

Articles in Wiki should basically not just address the already well informed but also the interested in a certain subjects. This article completely fails in that regard. The "three line" math sign is not widely known, therefore it is a hard to understand just that. Let's say you want to find the modular multiplicative inverse i of b in regard to mod n. (i is just a variable and not the mathematical sign for imaginary numbers!!!) Does this not just mean the following equation is correct: (b * i) mod n = 1 ??? This is basically what the result should be?! I solved it with a simple spreadsheet. It is simple. It is even primitive. Not a big deal! I am not a math genius, but I wanted to understand it exactly and this article does not provide the least help. Sometimes articles are just frustrating. Sorry!