search

cheran-senthil / PyRival

⚡ Competitive Programming Library
https://pyrival.readthedocs.io/
Apache License 2.0
1.15k stars 311 forks source link

Update tests for discrete log #36

Closed sgtlaugh closed 4 years ago

sgtlaugh commented 4 years ago

Changes

cheran-senthil commented 4 years ago

The tests are still useful, but I think we can stick to @bjorn-martinsson's code for discrete log since there is no gcd overhead there.

bjorn-martinsson commented 4 years ago

The tests are still useful, but I think we can stick to @bjorn-martinsson's code for discrete log since there is no gcd overhead there.

Just a small note about this, when I was reading @sgtlaugh code I thought about how one could make it simpler. After thinking about it I found that there is a super simple way to do it (without ever calling gcd or egcd), you can see it here https://github.com/cheran-senthil/PyRival/blob/master/pyrival/algebra/discrete_log.py .

Essentially the correctness of my algorithm boils down to this: Assume p^x is a prime power divisor of mod then we have 3 cases

  1. b divisible by p^x
  2. b divisible only by p^y, 0<y<x
  3. b is not divisible by p The important thing is that in case 2, the discrete log (if it exists) cannot be > sqrt(mod), (technically it should be > log2(mod)) So once you've checked all exponents of a <= sqrt(mod) You can't have case 2. Case 2 is the only tricky case.
Mukundan314 commented 4 years ago

I think splitting the test function into two function named test_discrete_log and test_discrete_log_corner_cases would be better.

sgtlaugh commented 4 years ago

The tests are still useful, but I think we can stick to @bjorn-martinsson's code for discrete log since there is no gcd overhead there.

Just a small note about this, when I was reading @sgtlaugh code I thought about how one could make it simpler. After thinking about it I found that there is a super simple way to do it (without ever calling gcd or egcd), you can see it here https://github.com/cheran-senthil/PyRival/blob/master/pyrival/algebra/discrete_log.py .

Essentially the correctness of my algorithm boils down to this: Assume p^x is a prime power divisor of mod then we have 3 cases

  1. b divisible by p^x
  2. b divisible only by p^y, 0<y<x
  3. b is not divisible by p The important thing is that in case 2, the discrete log (if it exists) cannot be > sqrt(mod), (technically it should be > log2(mod)) So once you've checked all exponents of a <= sqrt(mod) You can't have case 2. Case 2 is the only tricky case.

Just took a look. That should work and it's definitely better and simpler.

sgtlaugh commented 4 years ago

The tests are still useful, but I think we can stick to @bjorn-martinsson's code for discrete log since there is no gcd overhead there.

Sure, updated the PR