Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

crypto/rsa: doc: reword "coprime to" in doc comments #31721

Open
as opened this issue Apr 28, 2019 · 7 comments
Open

crypto/rsa: doc: reword "coprime to" in doc comments #31721

as opened this issue Apr 28, 2019 · 7 comments

Comments

@as
Copy link
Contributor

@as as commented Apr 28, 2019

I found this paragraph in the crypto/rsa docs:

https://github.com/golang/go/blob/master/src/crypto/rsa/rsa.go#L187-L191

	// Check that de ≡ 1 mod p-1, for each prime.
	// This implies that e is coprime to each p-1 as e has a multiplicative
	// inverse. Therefore e is coprime to lcm(p-1,q-1,r-1,...) =
	// exponent(ℤ/nℤ). It also implies that a^de ≡ a mod p as a^(p-1) ≡ 1
	// mod p. Thus a^de ≡ a mod n for all a coprime to n, as required.

It is a mistake to say x is coprime to y, because co and to convey the same thing. A number x, y can be coprime, but we say x is prime to y.

This is explicitly stated by Stewart in Galios Theory 3rd Edition (ISBN 1-58488-393-6), in Definition 3.14 on the topic of coprimes.

@jimmyfrasche
Copy link
Member

@jimmyfrasche jimmyfrasche commented Apr 28, 2019

Data point: I've always heard and said "x coprime to y". I don't recall ever hearing "x prime to y".

cc: @FiloSottile

@as
Copy link
Contributor Author

@as as commented Apr 29, 2019

@jimmyfrasche The more familiar utterance is "relatively prime to y", although my source text does not mention it

@bcmills bcmills added this to the Unplanned milestone May 22, 2019
@bcmills bcmills changed the title crypto/rsa: doc: reword incorrect misnomer "coprime to" crypto/rsa: doc: reword "coprime to" in doc comments May 22, 2019
@kurahaupo
Copy link

@kurahaupo kurahaupo commented Jun 15, 2019

I've usually heard it said as “X is co-prime with Y”, which follows from the general pattern in English of “X and Y are Z” being often interchangeable with “X is Z with Y”.

The usage queried here follows by combining that with another general pattern in 21st century English: to replace “with” with “to” in most common phrase patterns.

@smasher164
Copy link
Member

@smasher164 smasher164 commented Aug 5, 2019

If x and y are coprime, we also say that x is coprime to y, or that y is coprime to x.

Bourbaki, N. (2003). Algebra II: Chapters 4-7. Berlin: Springer-Verlag. A. VI. 14

I think it's fine the way it's currently written.

@as
Copy link
Contributor Author

@as as commented Aug 5, 2019

Stewart's text was published in 2015, and authors under the Bourbaki pen name publish their books in French. Is your 2003 source a translation of their original work?

@smasher164
Copy link
Member

@smasher164 smasher164 commented Aug 6, 2019

It is, yes, of their work in 1990, but that is only example. A google scholar search for "is prime to" AND "RSA" leads to 399 results, half of which oddly don't actually have the phrase "is prime to". However, a similar search for "is coprime to" AND "RSA" shows nearly 785 hits use this as standard terminology.

Taking a look at the original RSA paper, the terminology used is actually "x is relatively prime to y". I suspect that "x is coprime to y" became popular because of its terseness, as well as its ability to clearly communicate that these values are not individually prime. If we were to change anything, I'd gravitate toward "is relatively prime to".

@as
Copy link
Contributor Author

@as as commented Aug 6, 2019

I'd gravitate toward "is relatively prime to".

This seems like an agreeable compromise.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
6 participants