{"action":"created","issue":{"url":"https://api.github.com/repos/cartazio/arithmoi/issues/130","repository_url":"https://api.github.com/repos/cartazio/arithmoi","labels_url":"https://api.github.com/repos/cartazio/arithmoi/issues/130/labels{/name}","comments_url":"https://api.github.com/repos/cartazio/arithmoi/issues/130/comments","events_url":"https://api.github.com/repos/cartazio/arithmoi/issues/130/events","html_url":"https://github.com/cartazio/arithmoi/pull/130","id":352805696,"node_id":"MDExOlB1bGxSZXF1ZXN0MjEwMDIxODI3","number":130,"title":"(WIP) Discrete log and Dirichlet characters","user":{"login":"b-mehta","id":29959226,"node_id":"MDQ6VXNlcjI5OTU5MjI2","avatar_url":"https://avatars2.githubusercontent.com/u/29959226?v=4","gravatar_id":"","url":"https://api.github.com/users/b-mehta","html_url":"https://github.com/b-mehta","followers_url":"https://api.github.com/users/b-mehta/followers","following_url":"https://api.github.com/users/b-mehta/following{/other_user}","gists_url":"https://api.github.com/users/b-mehta/gists{/gist_id}","starred_url":"https://api.github.com/users/b-mehta/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/b-mehta/subscriptions","organizations_url":"https://api.github.com/users/b-mehta/orgs","repos_url":"https://api.github.com/users/b-mehta/repos","events_url":"https://api.github.com/users/b-mehta/events{/privacy}","received_events_url":"https://api.github.com/users/b-mehta/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":21,"created_at":"2018-08-22T05:13:39Z","updated_at":"2018-09-09T19:01:14Z","closed_at":null,"author_association":"CONTRIBUTOR","pull_request":{"url":"https://api.github.com/repos/cartazio/arithmoi/pulls/130","html_url":"https://github.com/cartazio/arithmoi/pull/130","diff_url":"https://github.com/cartazio/arithmoi/pull/130.diff","patch_url":"https://github.com/cartazio/arithmoi/pull/130.patch"},"body":"Discrete logarithms and Dirichlet characters. Resolves #88 and #119. In roughly this order, this is my plan for full efficient implementation of both.\r\n\r\n- [x] Added `MultMod` type to represent elements of the multiplicative group mod m, with Monoid instance. Added `PrimitiveRoot` type to represent primitive roots of the (cyclic) multiplicative group.\r\nNote these two types together make `discreteLogarithm` a total function. Partial constructors have been added and deconstructors. (I would like feedback on the name `MultMod`, I feel a better name is possible.)\r\n- [x] Amended primitive root code, testing, benching with the new type structures.\r\n- [x] Very simple discrete log code, with test and bench.\r\n- [x] Baby-step giant-step method for discrete logs.\r\n- [x] Additional testing and benching for discrete logs, with prime power cases included also.\r\n- [x] Refactor discrete logs to be efficient on prime powers, using Bach's method described [here](https://math.stackexchange.com/questions/1863037/discrete-logarithm-modulo-powers-of-a-small-prime) and [here](https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-186.pdf). (Also use the canonical isomorphism for double prime powers).\r\n- [x] Implement Pollard's rho algorithm for discrete logs with prime moduli (#129 would be helpful for this). Notably, Pollard's rho is a Las Vegas algorithm (which is why @Taneb's attempt in #110 did not always return success) so may need to run multiple times - experiment with starting inputs.\r\n- [ ] Write an internal discrete log function for moduli 2^k, which are necessary for Dirichlet characters (see Bach paper for efficient algorithm).\r\n- [ ] Implement `DirichletCharacter` type and constructor.\r\n- [ ] `RootOfUnity` type and `Semigroup` and `Monoid` instances.\r\n- [ ] `Bounded`, `Enum` (potentially `Show`) instances of `DirichletCharacter`.\r\n- [ ] Conversion of `DirichletCharacter` to function `Int -> RootOfUnity`."},"comment":{"url":"https://api.github.com/repos/cartazio/arithmoi/issues/comments/419737126","html_url":"https://github.com/cartazio/arithmoi/pull/130#issuecomment-419737126","issue_url":"https://api.github.com/repos/cartazio/arithmoi/issues/130","id":419737126,"node_id":"MDEyOklzc3VlQ29tbWVudDQxOTczNzEyNg==","user":{"login":"b-mehta","id":29959226,"node_id":"MDQ6VXNlcjI5OTU5MjI2","avatar_url":"https://avatars2.githubusercontent.com/u/29959226?v=4","gravatar_id":"","url":"https://api.github.com/users/b-mehta","html_url":"https://github.com/b-mehta","followers_url":"https://api.github.com/users/b-mehta/followers","following_url":"https://api.github.com/users/b-mehta/following{/other_user}","gists_url":"https://api.github.com/users/b-mehta/gists{/gist_id}","starred_url":"https://api.github.com/users/b-mehta/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/b-mehta/subscriptions","organizations_url":"https://api.github.com/users/b-mehta/orgs","repos_url":"https://api.github.com/users/b-mehta/repos","events_url":"https://api.github.com/users/b-mehta/events{/privacy}","received_events_url":"https://api.github.com/users/b-mehta/received_events","type":"User","site_admin":false},"created_at":"2018-09-09T19:01:14Z","updated_at":"2018-09-09T19:01:14Z","author_association":"CONTRIBUTOR","body":"That would be nice, but I fear that the probability of failure is genuinely tiny - testing all primes less than 7000 represents over 5 billion instances of the discrete log problem, and no failure has yet occured.\r\n\r\nPossibly, but BSGS uses IntMaps internally and right now BSGS is used anyway when the inputs are less than 10^8 so in that scenario, the values may not fit within an Int. In addition, if Maps are used instead, it is possible that massive maps are made and create memory issues instead.  I'd be more comfortable allowing more seeds instead."}}
{"actor":{"display_login":"b-mehta"}}