search

Bodigrim / arithmoi

Number theory: primes, arithmetic functions, modular computations, special sequences
http://hackage.haskell.org/package/arithmoi
MIT License
147 stars 40 forks source link

(WIP) Discrete logarithm #110

Closed Taneb closed 6 years ago

Taneb commented 6 years ago

This is the work I started at ZuriHac. It implements Pollard's rho algorithm to compute the discrete logarithm. This has the deficiency that there are some solutions it cannot find, such as 2^x == 7 (mod 9), which I would like to resolve before this PR gets merged.

Bodigrim commented 6 years ago

@Taneb just a gentle reminder that you intended to resolve remaining issues. Or we can merge as is and restrict inputs of discrete logarithm to primitive roots only.

Taneb commented 6 years ago

Sorry, I've been busier than I expected! :sweat_smile: Going to do some work on this tonight, though

Bodigrim commented 6 years ago

I think we can introduce a newtype 

newtype PrimitiveRoot n = PrimitiveRoot (Mod n)

and amend the signature of Math.NumberTheory.Moduli.PrimitiveRoot to 

isPrimitiveRoot
  :: KnownNat n => Mod n -> Maybe (PrimitiveRoot n)

Consequently, discreteLogarithm should allow only PrimitiveRoot as its second argument, 

discreteLogarithm :: (KnownNat m, Integral b) => Mod m -> PrimitiveRoot m -> Maybe b

This eliminates the current issue with logarithms by non-primitive base (Pollard's algorithm supposes that the base is primitive) without compromising performance or correctness.

Taneb commented 6 years ago

Oooh, that's a good idea. I'll implement that this evening

Bodigrim commented 6 years ago

@Taneb any chance to finish it soon?

Bodigrim commented 6 years ago

Closing, superseded by #130. Anyway, thanks for you efforts.

Taneb commented 6 years ago

Sorry I neglected this issue! I'm glad it's been solved by someone, I had... less time and headspace for this than I'd have liked

Bodigrim commented 6 years ago

It was a pleasure to work with you at ZuriHac.