{"action":"created","issue":{"url":"https://api.github.com/repos/lemire/rollinghashcpp/issues/6","repository_url":"https://api.github.com/repos/lemire/rollinghashcpp","labels_url":"https://api.github.com/repos/lemire/rollinghashcpp/issues/6/labels{/name}","comments_url":"https://api.github.com/repos/lemire/rollinghashcpp/issues/6/comments","events_url":"https://api.github.com/repos/lemire/rollinghashcpp/issues/6/events","html_url":"https://github.com/lemire/rollinghashcpp/issues/6","id":158570942,"number":6,"title":"GeneralHash: the default polynomial isn't really irreducible","user":{"login":"vcunat","id":1785925,"avatar_url":"https://avatars.githubusercontent.com/u/1785925?v=3","gravatar_id":"","url":"https://api.github.com/users/vcunat","html_url":"https://github.com/vcunat","followers_url":"https://api.github.com/users/vcunat/followers","following_url":"https://api.github.com/users/vcunat/following{/other_user}","gists_url":"https://api.github.com/users/vcunat/gists{/gist_id}","starred_url":"https://api.github.com/users/vcunat/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/vcunat/subscriptions","organizations_url":"https://api.github.com/users/vcunat/orgs","repos_url":"https://api.github.com/users/vcunat/repos","events_url":"https://api.github.com/users/vcunat/events{/privacy}","received_events_url":"https://api.github.com/users/vcunat/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2016-06-05T19:49:41Z","updated_at":"2016-06-05T21:42:34Z","closed_at":null,"body":"Hello (again). I wondered where you took the irreducible polynomials from, and unable to see that I tried to check them which [failed for the 19-degree one](http://www.wolframalpha.com/input/?i=factor+x^19+%2B+x^18+%2B+x^17+%2B+x^16+%2B+x^12+%2B+x^7+%2B+x^6+%2B+x^5+%2B+x^3+%2B+x^2+%2B+1+mod+2). The other one seems OK according to Wolfram. (EDITed the link not to drop the `+` characters.)\r\n\r\nI verified by different means that the factorization indeed does hold, e.g. `158543 ^ (158543<<1) ^ (158543<<2) == 987373`.\r\n\r\nFor speed testing there's most likely no impact, even though there are conditionals on some of the bits but those should still be uniform enough. And to be honest, most rolling-hash implementations use much worse functions, but still..."},"comment":{"url":"https://api.github.com/repos/lemire/rollinghashcpp/issues/comments/223839588","html_url":"https://github.com/lemire/rollinghashcpp/issues/6#issuecomment-223839588","issue_url":"https://api.github.com/repos/lemire/rollinghashcpp/issues/6","id":223839588,"user":{"login":"vcunat","id":1785925,"avatar_url":"https://avatars.githubusercontent.com/u/1785925?v=3","gravatar_id":"","url":"https://api.github.com/users/vcunat","html_url":"https://github.com/vcunat","followers_url":"https://api.github.com/users/vcunat/followers","following_url":"https://api.github.com/users/vcunat/following{/other_user}","gists_url":"https://api.github.com/users/vcunat/gists{/gist_id}","starred_url":"https://api.github.com/users/vcunat/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/vcunat/subscriptions","organizations_url":"https://api.github.com/users/vcunat/orgs","repos_url":"https://api.github.com/users/vcunat/repos","events_url":"https://api.github.com/users/vcunat/events{/privacy}","received_events_url":"https://api.github.com/users/vcunat/received_events","type":"User","site_admin":false},"created_at":"2016-06-05T21:42:34Z","updated_at":"2016-06-05T21:42:34Z","body":"Suggestion: this polynomial looks nice\r\nhttp://www.wolframalpha.com/input/?i=factor+x^0+x^1+x^2+x^5+x^6+x^7+x^9+x^11+x^14+x^19+x^20+x^21+x^22+x^24+x^27+x^30+x^32+mod+2\r\n\r\nI think there's little advantage in using smaller than 32-bit state for this algorithm, even on 32-bit-only machines (which are rare enough nowadays). In decimal representation it's 1232620263 (if without the x^32 bit).\r\n\r\nApart from being irreducible, it's also primitive, which might have some advantage, but I haven't given much thought to that and I'm really not so good in number theory anyway. I just chose a random line from a public list https://users.ece.cmu.edu/~koopman/lfsr/index.html"}}
{"actor":{"display_login":"vcunat"}}