)]}'
{
  "commit": "db41dc26f7265673b081bab5fad3cae6b48ac1f4",
  "tree": "a43ac179294ebc1c19e0780bc427cf1fb3dd4e39",
  "parents": [
    "a135fe1fad70e4f87b38b0adebd44d93da7eb173"
  ],
  "author": {
    "name": "David Benjamin",
    "email": "davidben@google.com",
    "time": "Thu Sep 11 12:40:04 2025 -0400"
  },
  "committer": {
    "name": "Boringssl LUCI CQ",
    "email": "boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com",
    "time": "Tue Sep 23 14:23:55 2025 -0700"
  },
  "message": "Use a simpler process to compute n0\n\nThis seems to be a relatively common trick.\nhttps://crypto.stackexchange.com/a/47496 and\nhttps://bearssl.org/bigint.html#montgomery-reduction-and-multiplication\nwere the clearest citations I could find.\n\nI modified it slightly. Normally you need n0 up to the precision of the\nword size you can easily multiply. We actually need double-word (64-bit)\nprecision on 32-bit architectures, due to the x86 assembly. (32-bit x86\nhas 64-bit multiplication in SSE2. We currently compute a 64-bit n0 on\nall 32-bit platforms but just ignore the upper half on the others.)\n\nSo we start by computing the 32-bit inverse, using uint32_t, then do one\nextra iteration in 64-bit. The recurrence can also be modified for the\nnegative inverse, which lets us do the negation while we\u0027re still\nsingle-precision.\n\nThis is also the technique described in\nhttps://en.wikipedia.org/wiki/Montgomery_modular_multiplication#Arithmetic_in_Montgomery_form\nas Hensel\u0027s lemma, but I\u0027m having a hard time following the extremely\ngeneralized description there.\n\nChange-Id: I08580cdd09929cebca723570ef44068304d5ac43\nReviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/82027\nReviewed-by: Lily Chen \u003cchlily@google.com\u003e\nAuto-Submit: David Benjamin \u003cdavidben@google.com\u003e\nCommit-Queue: David Benjamin \u003cdavidben@google.com\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "b2fa8390895f4e4f276b131d50435ad7f587e663",
      "old_mode": 33188,
      "old_path": "crypto/fipsmodule/bn/montgomery_inv.cc.inc",
      "new_id": "1c2b3986138de06b64c019c73d555a1e66ae5718",
      "new_mode": 33188,
      "new_path": "crypto/fipsmodule/bn/montgomery_inv.cc.inc"
    }
  ]
}