{"action":"created","comment":{"url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/pulls/comments/25564737","id":25564737,"diff_hunk":"@@ -290,14 +286,177 @@ sjcl.bn.prototype = {\n \n   /** this ^ x mod N */\n   powermod: function(x, N) {\n-    var result = new sjcl.bn(1), a = new sjcl.bn(this), k = new sjcl.bn(x);\n-    while (true) {\n-      if (k.limbs[0] & 1) { result = result.mulmod(a, N); }\n-      k.halveM();\n-      if (k.equals(0)) { break; }\n-      a = a.mulmod(a, N);\n-    }\n-    return result.normalize().reduce();\n+    x = new sjcl.bn(x);\n+    N = new sjcl.bn(N);\n+\n+    // Jump to montpowermod if possible.\n+    if ((N.limbs[0] & 1) == 1) {\n+      var montOut = this.montpowermod(x, N);\n+\n+      if (montOut != false) { return montOut; } // else go to slow powermod\n+    }\n+\n+    var i, j, l = x.normalize().trim().limbs, out = new this._class(1), pow = this;\n+\n+    for (i=0; i<l.length; i++) {\n+      for (j=0; j<this.radix; j++) {\n+        if (l[i] & (1<<j)) { out = out.mulmod(pow, N); }\n+        if (i == (l.length - 1) && l[i]>>(j + 1) == 0) { break; }\n+\n+        pow = pow.mulmod(pow, N);\n+      }\n+    }\n+\n+    return out;\n+  },\n+\n+  /** this ^ x mod N with Montomery reduction */\n+  montpowermod: function(x, N) {\n+    x = new sjcl.bn(x).normalize().trim();\n+    N = new sjcl.bn(N);\n+\n+    var i, j,\n+      radix = this.radix,\n+      out = new this._class(1),\n+      pow = this.copy();\n+\n+    // Generate R as a cap of N.\n+    var R, s, wind, bitsize = x.bitLength();\n+\n+    R = new sjcl.bn({\n+      limbs: N.copy().normalize().trim().limbs.map(function() { return 0; })\n+    });\n+\n+    for (s = this.radix; s > 0; s--) {\n+      if (((N.limbs[N.limbs.length - 1] >> s) & 1) == 1) {\n+        R.limbs[R.limbs.length - 1] = 1 << s;\n+        break;\n+      }\n+    }\n+\n+    // Calculate window size as a function of the exponent's size.\n+    if (bitsize == 0) { return this;\n+    } else if (bitsize < 18)  { wind = 1;\n+    } else if (bitsize < 48)  { wind = 3;\n+    } else if (bitsize < 144) { wind = 4;\n+    } else if (bitsize < 768) { wind = 5;\n+    } else { wind = 6; }\n+\n+    // Find R' and N' such that R * R' - N * N' = 1.\n+    var RR = R.copy(), NN = N.copy(), RP = new sjcl.bn(1), NP = new sjcl.bn(0), RT = R.copy();\n+\n+    while (RT.greaterEquals(1)) {\n+      RT.halveM();\n+\n+      if ((RP.limbs[0] & 1) == 0) {\n+        RP.halveM();\n+        NP.halveM();\n+      } else {\n+        RP.addM(NN);\n+        RP.halveM();\n+\n+        NP.halveM();\n+        NP.addM(RR);\n+      }\n+    }\n+\n+    RP = RP.normalize();\n+    NP = NP.normalize();\n+\n+    RR.doubleM()\n+    var R2 = RR.mulmod(RR, N);\n+\n+    // Check whether the invariant holds.\n+    // If it doesn't, we can't use Montgomery reduction on this modulus.\n+    if (!RR.mul(RP).sub(N.mul(NP)).equals(1)) {\n+      return false;\n+    }\n+\n+    var montIn = function(c) { return montMul(c, R2) },","path":"core/bn.js","position":316,"original_position":309,"commit_id":"bdc3cb6ec5a7090048c977166f1c8e0596ec3dc6","original_commit_id":"2ec84c73bc27710fed03423aea78aedd1a3c696f","user":{"login":"Bren2010","id":416022,"avatar_url":"https://avatars.githubusercontent.com/u/416022?v=3","gravatar_id":"","url":"https://api.github.com/users/Bren2010","html_url":"https://github.com/Bren2010","followers_url":"https://api.github.com/users/Bren2010/followers","following_url":"https://api.github.com/users/Bren2010/following{/other_user}","gists_url":"https://api.github.com/users/Bren2010/gists{/gist_id}","starred_url":"https://api.github.com/users/Bren2010/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Bren2010/subscriptions","organizations_url":"https://api.github.com/users/Bren2010/orgs","repos_url":"https://api.github.com/users/Bren2010/repos","events_url":"https://api.github.com/users/Bren2010/events{/privacy}","received_events_url":"https://api.github.com/users/Bren2010/received_events","type":"User","site_admin":false},"body":"@Nilos There's not really a clean way to do that... Those functions use the calculation of `R` and `N` from above.  If they were pulled out, you'd have to either pass in both which is weird because `R` isn't an independent parameter, it's directly dependent on `N`.  Just passing in `N` would mean wasting time re-calculating `R`.\r\n\r\nShould I just go with the creating-a-new-class idea?","created_at":"2015-03-01T06:47:12Z","updated_at":"2015-03-01T06:47:12Z","html_url":"https://github.com/bitwiseshiftleft/sjcl/pull/208#discussion_r25564737","pull_request_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/pulls/208","_links":{"self":{"href":"https://api.github.com/repos/bitwiseshiftleft/sjcl/pulls/comments/25564737"},"html":{"href":"https://github.com/bitwiseshiftleft/sjcl/pull/208#discussion_r25564737"},"pull_request":{"href":"https://api.github.com/repos/bitwiseshiftleft/sjcl/pulls/208"}}},"pull_request":{"url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/pulls/208","id":29970547,"html_url":"https://github.com/bitwiseshiftleft/sjcl/pull/208","diff_url":"https://github.com/bitwiseshiftleft/sjcl/pull/208.diff","patch_url":"https://github.com/bitwiseshiftleft/sjcl/pull/208.patch","issue_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/issues/208","number":208,"state":"open","locked":false,"title":"Montgomery Reduction","user":{"login":"Bren2010","id":416022,"avatar_url":"https://avatars.githubusercontent.com/u/416022?v=3","gravatar_id":"","url":"https://api.github.com/users/Bren2010","html_url":"https://github.com/Bren2010","followers_url":"https://api.github.com/users/Bren2010/followers","following_url":"https://api.github.com/users/Bren2010/following{/other_user}","gists_url":"https://api.github.com/users/Bren2010/gists{/gist_id}","starred_url":"https://api.github.com/users/Bren2010/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Bren2010/subscriptions","organizations_url":"https://api.github.com/users/Bren2010/orgs","repos_url":"https://api.github.com/users/Bren2010/repos","events_url":"https://api.github.com/users/Bren2010/events{/privacy}","received_events_url":"https://api.github.com/users/Bren2010/received_events","type":"User","site_admin":false},"body":"1.  (Same as before, with cleaner commit history) `sjcl.bn.power` will no longer freeze if it's not in a field and `sjcl.bn.powermod` is slightly faster.\r\n2.  Modular exponentiation with Montgomery reduction was implemented at `bn.montpowermod(x, N)`, and `bn.powermod(x, N)` defers to it when possible (when the modulus is odd).\r\n3.  The rest of the standard SRP group choices have been implemented because using them is somewhat practical now.\r\n\r\nHere are some *very* rough benchmarks I took from my iMac and Ubuntu laptop: (All using 32 byte secret keys, running the code sample from the top of issue #172)\r\n\r\nGroup Size |  iMac Time (s) | Laptop Time (s) |\r\n|:-------:|------:|------:|\r\n| 1024 | 0.03 | 0.08 |\r\n| 1536 | 0.07 | 0.16 |\r\n| 2048 | 0.11 | 0.26 |\r\n| 3072 | 0.22 | 0.55 |\r\n| 4096 | 0.40 | 0.95 |\r\n| 6144 | 0.80 | 2.00 |\r\n| 8192 | 1.30 | 3.50 |\r\n\r\nChrome is usually a tick faster than Firefox.  It'd be great if someone else can vouch for similar speeds.\r\n\r\nSupersedes pull request #203 and hopefully resolves issue #172.\r\n\r\n**Questions:**\r\n- Should this be re-implemented similar to the way pseudo-Mersenne primes are (which would get rid of all of the `bn.*mod(..., N)` methods)?  How should the modulus be passed in?\r\n- If the modulus is even, we could use the smallest viable pseudo-Mersenne prime--that would get fast modulo, but is there a way to divide by a pseudo-Mersenne prime efficiently?","created_at":"2015-02-25T09:06:25Z","updated_at":"2015-03-01T06:47:12Z","closed_at":null,"merged_at":null,"merge_commit_sha":"9d8e5059e9ea6e14adb704e0a82fc2331e40898a","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/pulls/208/commits","review_comments_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/pulls/208/comments","review_comment_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/pulls/comments{/number}","comments_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/issues/208/comments","statuses_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/statuses/bdc3cb6ec5a7090048c977166f1c8e0596ec3dc6","head":{"label":"Bren2010:bn-fix2","ref":"bn-fix2","sha":"bdc3cb6ec5a7090048c977166f1c8e0596ec3dc6","user":{"login":"Bren2010","id":416022,"avatar_url":"https://avatars.githubusercontent.com/u/416022?v=3","gravatar_id":"","url":"https://api.github.com/users/Bren2010","html_url":"https://github.com/Bren2010","followers_url":"https://api.github.com/users/Bren2010/followers","following_url":"https://api.github.com/users/Bren2010/following{/other_user}","gists_url":"https://api.github.com/users/Bren2010/gists{/gist_id}","starred_url":"https://api.github.com/users/Bren2010/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Bren2010/subscriptions","organizations_url":"https://api.github.com/users/Bren2010/orgs","repos_url":"https://api.github.com/users/Bren2010/repos","events_url":"https://api.github.com/users/Bren2010/events{/privacy}","received_events_url":"https://api.github.com/users/Bren2010/received_events","type":"User","site_admin":false},"repo":{"id":26035105,"name":"sjcl","full_name":"Bren2010/sjcl","owner":{"login":"Bren2010","id":416022,"avatar_url":"https://avatars.githubusercontent.com/u/416022?v=3","gravatar_id":"","url":"https://api.github.com/users/Bren2010","html_url":"https://github.com/Bren2010","followers_url":"https://api.github.com/users/Bren2010/followers","following_url":"https://api.github.com/users/Bren2010/following{/other_user}","gists_url":"https://api.github.com/users/Bren2010/gists{/gist_id}","starred_url":"https://api.github.com/users/Bren2010/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Bren2010/subscriptions","organizations_url":"https://api.github.com/users/Bren2010/orgs","repos_url":"https://api.github.com/users/Bren2010/repos","events_url":"https://api.github.com/users/Bren2010/events{/privacy}","received_events_url":"https://api.github.com/users/Bren2010/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/Bren2010/sjcl","description":"Stanford Javascript Crypto Library","fork":true,"url":"https://api.github.com/repos/Bren2010/sjcl","forks_url":"https://api.github.com/repos/Bren2010/sjcl/forks","keys_url":"https://api.github.com/repos/Bren2010/sjcl/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Bren2010/sjcl/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Bren2010/sjcl/teams","hooks_url":"https://api.github.com/repos/Bren2010/sjcl/hooks","issue_events_url":"https://api.github.com/repos/Bren2010/sjcl/issues/events{/number}","events_url":"https://api.github.com/repos/Bren2010/sjcl/events","assignees_url":"https://api.github.com/repos/Bren2010/sjcl/assignees{/user}","branches_url":"https://api.github.com/repos/Bren2010/sjcl/branches{/branch}","tags_url":"https://api.github.com/repos/Bren2010/sjcl/tags","blobs_url":"https://api.github.com/repos/Bren2010/sjcl/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Bren2010/sjcl/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Bren2010/sjcl/git/refs{/sha}","trees_url":"https://api.github.com/repos/Bren2010/sjcl/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Bren2010/sjcl/statuses/{sha}","languages_url":"https://api.github.com/repos/Bren2010/sjcl/languages","stargazers_url":"https://api.github.com/repos/Bren2010/sjcl/stargazers","contributors_url":"https://api.github.com/repos/Bren2010/sjcl/contributors","subscribers_url":"https://api.github.com/repos/Bren2010/sjcl/subscribers","subscription_url":"https://api.github.com/repos/Bren2010/sjcl/subscription","commits_url":"https://api.github.com/repos/Bren2010/sjcl/commits{/sha}","git_commits_url":"https://api.github.com/repos/Bren2010/sjcl/git/commits{/sha}","comments_url":"https://api.github.com/repos/Bren2010/sjcl/comments{/number}","issue_comment_url":"https://api.github.com/repos/Bren2010/sjcl/issues/comments{/number}","contents_url":"https://api.github.com/repos/Bren2010/sjcl/contents/{+path}","compare_url":"https://api.github.com/repos/Bren2010/sjcl/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Bren2010/sjcl/merges","archive_url":"https://api.github.com/repos/Bren2010/sjcl/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Bren2010/sjcl/downloads","issues_url":"https://api.github.com/repos/Bren2010/sjcl/issues{/number}","pulls_url":"https://api.github.com/repos/Bren2010/sjcl/pulls{/number}","milestones_url":"https://api.github.com/repos/Bren2010/sjcl/milestones{/number}","notifications_url":"https://api.github.com/repos/Bren2010/sjcl/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Bren2010/sjcl/labels{/name}","releases_url":"https://api.github.com/repos/Bren2010/sjcl/releases{/id}","created_at":"2014-10-31T22:25:20Z","updated_at":"2015-02-25T00:19:08Z","pushed_at":"2015-03-01T06:32:40Z","git_url":"git://github.com/Bren2010/sjcl.git","ssh_url":"git@github.com:Bren2010/sjcl.git","clone_url":"https://github.com/Bren2010/sjcl.git","svn_url":"https://github.com/Bren2010/sjcl","homepage":"http://bitwiseshiftleft.github.com/sjcl/","size":12841,"stargazers_count":0,"watchers_count":0,"language":"JavaScript","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"bitwiseshiftleft:master","ref":"master","sha":"bf6b8600614ada54beb2f55161de98e0d7acdee6","user":{"login":"bitwiseshiftleft","id":288092,"avatar_url":"https://avatars.githubusercontent.com/u/288092?v=3","gravatar_id":"","url":"https://api.github.com/users/bitwiseshiftleft","html_url":"https://github.com/bitwiseshiftleft","followers_url":"https://api.github.com/users/bitwiseshiftleft/followers","following_url":"https://api.github.com/users/bitwiseshiftleft/following{/other_user}","gists_url":"https://api.github.com/users/bitwiseshiftleft/gists{/gist_id}","starred_url":"https://api.github.com/users/bitwiseshiftleft/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bitwiseshiftleft/subscriptions","organizations_url":"https://api.github.com/users/bitwiseshiftleft/orgs","repos_url":"https://api.github.com/users/bitwiseshiftleft/repos","events_url":"https://api.github.com/users/bitwiseshiftleft/events{/privacy}","received_events_url":"https://api.github.com/users/bitwiseshiftleft/received_events","type":"User","site_admin":false},"repo":{"id":688208,"name":"sjcl","full_name":"bitwiseshiftleft/sjcl","owner":{"login":"bitwiseshiftleft","id":288092,"avatar_url":"https://avatars.githubusercontent.com/u/288092?v=3","gravatar_id":"","url":"https://api.github.com/users/bitwiseshiftleft","html_url":"https://github.com/bitwiseshiftleft","followers_url":"https://api.github.com/users/bitwiseshiftleft/followers","following_url":"https://api.github.com/users/bitwiseshiftleft/following{/other_user}","gists_url":"https://api.github.com/users/bitwiseshiftleft/gists{/gist_id}","starred_url":"https://api.github.com/users/bitwiseshiftleft/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bitwiseshiftleft/subscriptions","organizations_url":"https://api.github.com/users/bitwiseshiftleft/orgs","repos_url":"https://api.github.com/users/bitwiseshiftleft/repos","events_url":"https://api.github.com/users/bitwiseshiftleft/events{/privacy}","received_events_url":"https://api.github.com/users/bitwiseshiftleft/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/bitwiseshiftleft/sjcl","description":"Stanford Javascript Crypto Library","fork":false,"url":"https://api.github.com/repos/bitwiseshiftleft/sjcl","forks_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/forks","keys_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/keys{/key_id}","collaborators_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/teams","hooks_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/hooks","issue_events_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/issues/events{/number}","events_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/events","assignees_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/assignees{/user}","branches_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/branches{/branch}","tags_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/tags","blobs_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/git/refs{/sha}","trees_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/git/trees{/sha}","statuses_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/statuses/{sha}","languages_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/languages","stargazers_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/stargazers","contributors_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/contributors","subscribers_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/subscribers","subscription_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/subscription","commits_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/commits{/sha}","git_commits_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/git/commits{/sha}","comments_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/comments{/number}","issue_comment_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/issues/comments{/number}","contents_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/contents/{+path}","compare_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/compare/{base}...{head}","merges_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/merges","archive_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/downloads","issues_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/issues{/number}","pulls_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/pulls{/number}","milestones_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/milestones{/number}","notifications_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/labels{/name}","releases_url":"https://api.github.com/repos/bitwiseshiftleft/sjcl/releases{/id}","created_at":"2010-05-26T22:12:06Z","updated_at":"2015-03-01T06:21:37Z","pushed_at":"2015-02-28T21:00:34Z","git_url":"git://github.com/bitwiseshiftleft/sjcl.git","ssh_url":"git@github.com:bitwiseshiftleft/sjcl.git","clone_url":"https://github.com/bitwiseshiftleft/sjcl.git","svn_url":"https://github.com/bitwiseshiftleft/sjcl","homepage":"http://bitwiseshiftleft.github.com/sjcl/","size":21122,"stargazers_count":2608,"watchers_count":2608,"language":"JavaScript","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":325,"mirror_url":null,"open_issues_count":47,"forks":325,"open_issues":47,"watchers":2608,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/bitwiseshiftleft/sjcl/pulls/208"},"html":{"href":"https://github.com/bitwiseshiftleft/sjcl/pull/208"},"issue":{"href":"https://api.github.com/repos/bitwiseshiftleft/sjcl/issues/208"},"comments":{"href":"https://api.github.com/repos/bitwiseshiftleft/sjcl/issues/208/comments"},"review_comments":{"href":"https://api.github.com/repos/bitwiseshiftleft/sjcl/pulls/208/comments"},"review_comment":{"href":"https://api.github.com/repos/bitwiseshiftleft/sjcl/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/bitwiseshiftleft/sjcl/pulls/208/commits"},"statuses":{"href":"https://api.github.com/repos/bitwiseshiftleft/sjcl/statuses/bdc3cb6ec5a7090048c977166f1c8e0596ec3dc6"}}}}