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

math/big: ModInverse with modulus zero is undefined #47606

Open
FiloSottile opened this issue Aug 9, 2021 · 5 comments
Open

math/big: ModInverse with modulus zero is undefined #47606

FiloSottile opened this issue Aug 9, 2021 · 5 comments
Assignees
Labels
NeedsFix The path to resolution is known, but the work has not been done.
Milestone

Comments

@FiloSottile
Copy link
Contributor

FiloSottile commented Aug 9, 2021

ModInverse is defined for all values of g, and for positive and negative values n, but not for a zero n.

ModInverse sets z to the multiplicative inverse of g in the ring ℤ/nℤ
and returns z. If g and n are not relatively prime, g has no multiplicative
inverse in the ring ℤ/nℤ. In this case, z is unchanged and the return value
is nil.

The ring of numbers modulo zero does not exist, and being coprime with zero is meaningless, so the current docs don't cover it.

Arguably, ModInverse should always panic when the modulo is zero, but currently it returns nil for g > 1, returns 1 for g = 1, returns nil for g = 0, and panics for g < 0. Turning a non-panic into a panic for the sake of consistency is asking for trouble, so we should just make it return nil consistently for n = 0.

This could break programs that try to dereference the return value of ModInverse(1, 0), but that feels like a specific enough condition that programs won't have come to rely on it #famouslastwords.

@FiloSottile FiloSottile added the NeedsFix The path to resolution is known, but the work has not been done. label Aug 9, 2021
@FiloSottile FiloSottile added this to the Go1.18 milestone Aug 9, 2021
@gunadhya
Copy link

Hi @FiloSottile, I'd like to work on this issue.

@gopherbot
Copy link

Change https://golang.org/cl/342211 mentions this issue: big/int: Explicit checks in ModInverse for g modulo n=0

@odeke-em
Copy link
Member

Thank you for filing this issue @FiloSottile, and thank you @ok-john for sending the CL https://go-review.googlesource.com/c/go/+/342211/

This issue is marked for Go1.18, but the CL was marked with "Wait-Release". Shall we roll this over to Go1.19 or should we make the breaking change to return nil if the modulus is zero. Now one reservation here is that the internal code has a comment that its internal implementation of GCD expects the parameters to be > 0. Should we perhaps instead document this issue or just wait until Go1.19. What do you think @griesemer @ianlancetaylor?

@odeke-em
Copy link
Member

odeke-em commented Jan 6, 2022

Alright, I shall make the call to move this to the Go1.19 milestone as per the CL labelling and given that it is quite late in the cycle for a breakiing change.

@odeke-em odeke-em modified the milestones: Go1.18, Go1.19 Jan 6, 2022
@ianlancetaylor
Copy link
Contributor

CC @golang/security

Looks like this didn't make 1.19. Moving to backlog. Please recategorize as appropriate.

@ianlancetaylor ianlancetaylor modified the milestones: Go1.19, Backlog Jun 24, 2022
@julieqiu julieqiu modified the milestones: Backlog, Go1.20 Jul 18, 2022
@gopherbot gopherbot modified the milestones: Go1.20, Go1.21 Feb 1, 2023
@gopherbot gopherbot modified the milestones: Go1.21, Go1.22 Aug 8, 2023
@odeke-em odeke-em modified the milestones: Go1.22, Go1.23 Feb 5, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsFix The path to resolution is known, but the work has not been done.
Projects
Status: No status
Development

Successfully merging a pull request may close this issue.

7 participants