Scalar.hs (30444B)
1 {-# LANGUAGE BangPatterns #-} 2 {-# LANGUAGE MagicHash #-} 3 {-# LANGUAGE NumericUnderscores #-} 4 {-# LANGUAGE ViewPatterns #-} 5 {-# LANGUAGE UnboxedSums #-} 6 {-# LANGUAGE UnboxedTuples #-} 7 {-# LANGUAGE UnliftedNewtypes #-} 8 9 -- | 10 -- Module: Numeric.Montgomery.Secp256k1.Scalar 11 -- Copyright: (c) 2025 Jared Tobin 12 -- License: MIT 13 -- Maintainer: Jared Tobin <jared@ppad.tech> 14 -- 15 -- Montgomery form 'Wider' words, as well as arithmetic operations, with 16 -- domain derived from the secp256k1 elliptic curve scalar group order. 17 18 module Numeric.Montgomery.Secp256k1.Scalar ( 19 -- * Montgomery form, secp256k1 scalar group order modulus 20 Montgomery(..) 21 , render 22 , to_vartime 23 , from_vartime 24 , zero 25 , one 26 27 -- * Comparison 28 , eq 29 , eq_vartime 30 31 -- * Reduction and retrieval 32 , redc 33 , retr 34 , redc# 35 , retr# 36 37 -- * Constant-time selection 38 , select# 39 , select 40 41 -- * Montgomery arithmetic 42 , add 43 , add# 44 , sub 45 , sub# 46 , mul 47 , mul# 48 , sqr 49 , sqr# 50 , neg 51 , neg# 52 , inv 53 , inv# 54 , exp 55 , odd# 56 , odd_vartime 57 ) where 58 59 import Control.DeepSeq 60 import qualified Data.Choice as C 61 import Data.Word.Limb (Limb(..)) 62 import qualified Data.Word.Limb as L 63 import qualified Data.Word.Wide as W 64 import Data.Word.Wider (Wider(..)) 65 import qualified Data.Word.Wider as WW 66 import GHC.Exts (Word(..)) 67 import Prelude hiding (or, and, not, exp) 68 69 -- montgomery arithmetic, specialized to the secp256k1 scalar group order 70 -- 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 71 72 -- | Montgomery-form 'Wider' words, on the Montgomery domain defined by 73 -- the secp256k1 scalar group order. 74 -- 75 -- >>> let one = 1 :: Montgomery 76 -- >>> one 77 -- 1 78 -- >>> putStrLn (render one) 79 -- (4624529908474429119, 4994812053365940164, 1, 0) 80 data Montgomery = Montgomery !(# Limb, Limb, Limb, Limb #) 81 82 instance Show Montgomery where 83 show = show . from_vartime 84 85 -- | Render a 'Montgomery' value as a 'String', showing its individual 86 -- 'Limb's. 87 -- 88 -- >>> putStrLn (render 1) 89 -- (4624529908474429119, 4994812053365940164, 1, 0) 90 render :: Montgomery -> String 91 render (Montgomery (# Limb a, Limb b, Limb c, Limb d #)) = 92 "(" <> show (W# a) <> ", " <> show (W# b) <> ", " 93 <> show (W# c) <> ", " <> show (W# d) <> ")" 94 95 -- | Note that 'fromInteger' necessarily runs in variable time due 96 -- to conversion from the variable-size, potentially heap-allocated 97 -- 'Integer' type. 98 instance Num Montgomery where 99 a + b = add a b 100 a - b = sub a b 101 a * b = mul a b 102 negate a = neg a 103 abs = id 104 fromInteger = to_vartime . WW.to_vartime 105 signum (Montgomery (# l0, l1, l2, l3 #)) = 106 let !(Limb l) = l0 `L.or#` l1 `L.or#` l2 `L.or#` l3 107 !n = C.from_word_nonzero# l 108 !b = C.to_word# n 109 in Montgomery (# Limb b, Limb 0##, Limb 0##, Limb 0## #) 110 111 instance NFData Montgomery where 112 rnf (Montgomery a) = case a of (# _, _, _, _ #) -> () 113 114 -- utilities ------------------------------------------------------------------ 115 116 -- Wide wrapping addition, when addend is only a limb. 117 wadd_w# :: (# Limb, Limb #) -> Limb -> (# Limb, Limb #) 118 wadd_w# (# x_lo, x_hi #) y_lo = 119 let !(# s0, c0 #) = L.add_o# x_lo y_lo 120 !(# s1, _ #) = L.add_o# x_hi c0 121 in (# s0, s1 #) 122 {-# INLINE wadd_w# #-} 123 124 -- Truncate a wide word to a 'Limb'. 125 lo :: (# Limb, Limb #) -> Limb 126 lo (# l, _ #) = l 127 {-# INLINE lo #-} 128 129 -- comparison ----------------------------------------------------------------- 130 131 -- | Constant-time equality comparison. 132 eq :: Montgomery -> Montgomery -> C.Choice 133 eq 134 (Montgomery (# Limb a0, Limb a1, Limb a2, Limb a3 #)) 135 (Montgomery (# Limb b0, Limb b1, Limb b2, Limb b3 #)) 136 = C.eq_wider# (# a0, a1, a2, a3 #) (# b0, b1, b2, b3 #) 137 {-# INLINE eq #-} 138 139 -- | Variable-time equality comparison. 140 eq_vartime :: Montgomery -> Montgomery -> Bool 141 eq_vartime (Montgomery (Wider -> a)) (Montgomery (Wider -> b)) = 142 WW.eq_vartime a b 143 144 -- innards -------------------------------------------------------------------- 145 146 redc_inner# 147 :: (# Limb, Limb, Limb, Limb #) -- ^ upper limbs 148 -> (# Limb, Limb, Limb, Limb #) -- ^ lower limbs 149 -> (# (# Limb, Limb, Limb, Limb #), Limb #) -- ^ upper limbs, meta-carry 150 redc_inner# (# u0, u1, u2, u3 #) (# l0, l1, l2, l3 #) = 151 let !(# m0, m1, m2, m3 #) = 152 (# Limb 0xBFD25E8CD0364141##, Limb 0xBAAEDCE6AF48A03B## 153 , Limb 0xFFFFFFFFFFFFFFFE##, Limb 0xFFFFFFFFFFFFFFFF## #) 154 !n = Limb 0x4B0DFF665588B13F## 155 !w_0 = L.mul_w# l0 n 156 !(# _, c_00 #) = L.mac# w_0 m0 l0 (Limb 0##) 157 !(# l0_1, c_01 #) = L.mac# w_0 m1 l1 c_00 158 !(# l0_2, c_02 #) = L.mac# w_0 m2 l2 c_01 159 !(# l0_3, c_03 #) = L.mac# w_0 m3 l3 c_02 160 !(# u_0, mc_0 #) = L.add_c# u0 c_03 (Limb 0##) 161 !w_1 = L.mul_w# l0_1 n 162 !(# _, c_10 #) = L.mac# w_1 m0 l0_1 (Limb 0##) 163 !(# l1_1, c_11 #) = L.mac# w_1 m1 l0_2 c_10 164 !(# l1_2, c_12 #) = L.mac# w_1 m2 l0_3 c_11 165 !(# u1_3, c_13 #) = L.mac# w_1 m3 u_0 c_12 166 !(# u_1, mc_1 #) = L.add_c# u1 c_13 mc_0 167 !w_2 = L.mul_w# l1_1 n 168 !(# _, c_20 #) = L.mac# w_2 m0 l1_1 (Limb 0##) 169 !(# l2_1, c_21 #) = L.mac# w_2 m1 l1_2 c_20 170 !(# u2_2, c_22 #) = L.mac# w_2 m2 u1_3 c_21 171 !(# u2_3, c_23 #) = L.mac# w_2 m3 u_1 c_22 172 !(# u_2, mc_2 #) = L.add_c# u2 c_23 mc_1 173 !w_3 = L.mul_w# l2_1 n 174 !(# _, c_30 #) = L.mac# w_3 m0 l2_1 (Limb 0##) 175 !(# u3_1, c_31 #) = L.mac# w_3 m1 u2_2 c_30 176 !(# u3_2, c_32 #) = L.mac# w_3 m2 u2_3 c_31 177 !(# u3_3, c_33 #) = L.mac# w_3 m3 u_2 c_32 178 !(# u_3, mc_3 #) = L.add_c# u3 c_33 mc_2 179 in (# (# u3_1, u3_2, u3_3, u_3 #), mc_3 #) 180 {-# INLINE redc_inner# #-} 181 182 redc# 183 :: (# Limb, Limb, Limb, Limb #) -- ^ lower limbs 184 -> (# Limb, Limb, Limb, Limb #) -- ^ upper limbs 185 -> (# Limb, Limb, Limb, Limb #) -- ^ result 186 redc# l u = 187 let -- group order 188 !m = (# Limb 0xBFD25E8CD0364141##, Limb 0xBAAEDCE6AF48A03B## 189 , Limb 0xFFFFFFFFFFFFFFFE##, Limb 0xFFFFFFFFFFFFFFFF## #) 190 !(# nu, mc #) = redc_inner# u l 191 in WW.sub_mod_c# nu mc m m 192 {-# INLINE redc# #-} 193 194 -- | Montgomery reduction. 195 -- 196 -- The first argument represents the low words, and the second the 197 -- high words, of an extra-large eight-limb word in Montgomery form. 198 redc 199 :: Montgomery -- ^ low wider-word, Montgomery form 200 -> Montgomery -- ^ high wider-word, Montgomery form 201 -> Montgomery -- ^ reduced value 202 redc (Montgomery l) (Montgomery u) = 203 let !res = redc# l u 204 in (Montgomery res) 205 206 retr_inner# 207 :: (# Limb, Limb, Limb, Limb #) -- ^ value in montgomery form 208 -> (# Limb, Limb, Limb, Limb #) -- ^ retrieved value 209 retr_inner# (# x0, x1, x2, x3 #) = 210 let !(# m0, m1, m2, m3 #) = 211 (# Limb 0xBFD25E8CD0364141##, Limb 0xBAAEDCE6AF48A03B## 212 , Limb 0xFFFFFFFFFFFFFFFE##, Limb 0xFFFFFFFFFFFFFFFF## #) 213 !n = Limb 0x4B0DFF665588B13F## 214 !u_0 = L.mul_w# x0 n 215 !(# _, o0 #) = L.mac# u_0 m0 x0 (Limb 0##) 216 !(# o0_1, p0_1 #) = L.mac# u_0 m1 (Limb 0##) o0 217 !(# p0_2, q0_2 #) = L.mac# u_0 m2 (Limb 0##) p0_1 218 !(# q0_3, r0_3 #) = L.mac# u_0 m3 (Limb 0##) q0_2 219 !u_1 = L.mul_w# (L.add_w# o0_1 x1) n 220 !(# _, o1 #) = L.mac# u_1 m0 x1 o0_1 221 !(# o1_1, p1_1 #) = L.mac# u_1 m1 p0_2 o1 222 !(# p1_2, q1_2 #) = L.mac# u_1 m2 q0_3 p1_1 223 !(# q1_3, r1_3 #) = L.mac# u_1 m3 r0_3 q1_2 224 !u_2 = L.mul_w# (L.add_w# o1_1 x2) n 225 !(# _, o2 #) = L.mac# u_2 m0 x2 o1_1 226 !(# o2_1, p2_1 #) = L.mac# u_2 m1 p1_2 o2 227 !(# p2_2, q2_2 #) = L.mac# u_2 m2 q1_3 p2_1 228 !(# q2_3, r2_3 #) = L.mac# u_2 m3 r1_3 q2_2 229 !u_3 = L.mul_w# (L.add_w# o2_1 x3) n 230 !(# _, o3 #) = L.mac# u_3 m0 x3 o2_1 231 !(# o3_1, p3_1 #) = L.mac# u_3 m1 p2_2 o3 232 !(# p3_2, q3_2 #) = L.mac# u_3 m2 q2_3 p3_1 233 !(# q3_3, r3_3 #) = L.mac# u_3 m3 r2_3 q3_2 234 in (# o3_1, p3_2, q3_3, r3_3 #) 235 {-# INLINE retr_inner# #-} 236 237 retr# 238 :: (# Limb, Limb, Limb, Limb #) 239 -> (# Limb, Limb, Limb, Limb #) 240 retr# f = retr_inner# f 241 {-# INLINE retr# #-} 242 243 -- | Retrieve a 'Montgomery' value from the Montgomery domain, producing 244 -- a 'Wider' word. 245 retr 246 :: Montgomery -- ^ value in Montgomery form 247 -> Wider -- ^ retrieved value 248 retr (Montgomery f) = 249 let !res = retr# f 250 in (Wider res) 251 252 -- | Montgomery multiplication (FIOS), without conditional subtract. 253 mul_inner# 254 :: (# Limb, Limb, Limb, Limb #) -- ^ x 255 -> (# Limb, Limb, Limb, Limb #) -- ^ y 256 -> (# (# Limb, Limb, Limb, Limb #), Limb #) -- ^ product, meta-carry 257 mul_inner# (# x0, x1, x2, x3 #) (# y0, y1, y2, y3 #) = 258 let !(# m0, m1, m2, m3 #) = 259 (# Limb 0xBFD25E8CD0364141##, Limb 0xBAAEDCE6AF48A03B## 260 , Limb 0xFFFFFFFFFFFFFFFE##, Limb 0xFFFFFFFFFFFFFFFF## #) 261 !n = Limb 0x4B0DFF665588B13F## 262 !axy0 = L.mul_c# x0 y0 263 !u0 = L.mul_w# (lo axy0) n 264 !(# (# _, a0 #), c0 #) = W.add_o# (L.mul_c# u0 m0) axy0 265 !carry0 = (# a0, c0 #) 266 !axy0_1 = L.mul_c# x0 y1 267 !umc0_1 = W.add_w# (L.mul_c# u0 m1) carry0 268 !(# (# o0, ab0_1 #), c0_1 #) = W.add_o# axy0_1 umc0_1 269 !carry0_1 = (# ab0_1, c0_1 #) 270 !axy0_2 = L.mul_c# x0 y2 271 !umc0_2 = W.add_w# (L.mul_c# u0 m2) carry0_1 272 !(# (# p0, ab0_2 #), c0_2 #) = W.add_o# axy0_2 umc0_2 273 !carry0_2 = (# ab0_2, c0_2 #) 274 !axy0_3 = L.mul_c# x0 y3 275 !umc0_3 = W.add_w# (L.mul_c# u0 m3) carry0_2 276 !(# (# q0, ab0_3 #), c0_3 #) = W.add_o# axy0_3 umc0_3 277 !carry0_3 = (# ab0_3, c0_3 #) 278 !(# r0, mc0 #) = carry0_3 279 !axy1 = wadd_w# (L.mul_c# x1 y0) o0 280 !u1 = L.mul_w# (lo axy1) n 281 !(# (# _, a1 #), c1 #) = W.add_o# (L.mul_c# u1 m0) axy1 282 !carry1 = (# a1, c1 #) 283 !axy1_1 = wadd_w# (L.mul_c# x1 y1) p0 284 !umc1_1 = W.add_w# (L.mul_c# u1 m1) carry1 285 !(# (# o1, ab1_1 #), c1_1 #) = W.add_o# axy1_1 umc1_1 286 !carry1_1 = (# ab1_1, c1_1 #) 287 !axy1_2 = wadd_w# (L.mul_c# x1 y2) q0 288 !umc1_2 = W.add_w# (L.mul_c# u1 m2) carry1_1 289 !(# (# p1, ab1_2 #), c1_2 #) = W.add_o# axy1_2 umc1_2 290 !carry1_2 = (# ab1_2, c1_2 #) 291 !axy1_3 = wadd_w# (L.mul_c# x1 y3) r0 292 !umc1_3 = W.add_w# (L.mul_c# u1 m3) carry1_2 293 !(# (# q1, ab1_3 #), c1_3 #) = W.add_o# axy1_3 umc1_3 294 !carry1_3 = (# ab1_3, c1_3 #) 295 !(# r1, mc1 #) = wadd_w# carry1_3 mc0 296 !axy2 = wadd_w# (L.mul_c# x2 y0) o1 297 !u2 = L.mul_w# (lo axy2) n 298 !(# (# _, a2 #), c2 #) = W.add_o# (L.mul_c# u2 m0) axy2 299 !carry2 = (# a2, c2 #) 300 !axy2_1 = wadd_w# (L.mul_c# x2 y1) p1 301 !umc2_1 = W.add_w# (L.mul_c# u2 m1) carry2 302 !(# (# o2, ab2_1 #), c2_1 #) = W.add_o# axy2_1 umc2_1 303 !carry2_1 = (# ab2_1, c2_1 #) 304 !axy2_2 = wadd_w# (L.mul_c# x2 y2) q1 305 !umc2_2 = W.add_w# (L.mul_c# u2 m2) carry2_1 306 !(# (# p2, ab2_2 #), c2_2 #) = W.add_o# axy2_2 umc2_2 307 !carry2_2 = (# ab2_2, c2_2 #) 308 !axy2_3 = wadd_w# (L.mul_c# x2 y3) r1 309 !umc2_3 = W.add_w# (L.mul_c# u2 m3) carry2_2 310 !(# (# q2, ab2_3 #), c2_3 #) = W.add_o# axy2_3 umc2_3 311 !carry2_3 = (# ab2_3, c2_3 #) 312 !(# r2, mc2 #) = wadd_w# carry2_3 mc1 313 !axy3 = wadd_w# (L.mul_c# x3 y0) o2 314 !u3 = L.mul_w# (lo axy3) n 315 !(# (# _, a3 #), c3 #) = W.add_o# (L.mul_c# u3 m0) axy3 316 !carry3 = (# a3, c3 #) 317 !axy3_1 = wadd_w# (L.mul_c# x3 y1) p2 318 !umc3_1 = W.add_w# (L.mul_c# u3 m1) carry3 319 !(# (# o3, ab3_1 #), c3_1 #) = W.add_o# axy3_1 umc3_1 320 !carry3_1 = (# ab3_1, c3_1 #) 321 !axy3_2 = wadd_w# (L.mul_c# x3 y2) q2 322 !umc3_2 = W.add_w# (L.mul_c# u3 m2) carry3_1 323 !(# (# p3, ab3_2 #), c3_2 #) = W.add_o# axy3_2 umc3_2 324 !carry3_2 = (# ab3_2, c3_2 #) 325 !axy3_3 = wadd_w# (L.mul_c# x3 y3) r2 326 !umc3_3 = W.add_w# (L.mul_c# u3 m3) carry3_2 327 !(# (# q3, ab3_3 #), c3_3 #) = W.add_o# axy3_3 umc3_3 328 !carry3_3 = (# ab3_3, c3_3 #) 329 !(# r3, mc3 #) = wadd_w# carry3_3 mc2 330 in (# (# o3, p3, q3, r3 #), mc3 #) 331 {-# INLINE mul_inner# #-} 332 333 mul# 334 :: (# Limb, Limb, Limb, Limb #) 335 -> (# Limb, Limb, Limb, Limb #) 336 -> (# Limb, Limb, Limb, Limb #) 337 mul# a b = 338 let -- group order 339 !m = (# Limb 0xBFD25E8CD0364141##, Limb 0xBAAEDCE6AF48A03B## 340 , Limb 0xFFFFFFFFFFFFFFFE##, Limb 0xFFFFFFFFFFFFFFFF## #) 341 !(# nu, mc #) = mul_inner# a b 342 in WW.sub_mod_c# nu mc m m 343 {-# NOINLINE mul# #-} -- cannot be inlined without exploding comp time 344 345 -- | Multiplication in the Montgomery domain. 346 -- 347 -- Note that 'Montgomery' is an instance of 'Num', so you can use '*' 348 -- to apply this function. 349 -- 350 -- >>> 1 * 1 :: Montgomery 351 -- 1 352 mul 353 :: Montgomery -- ^ multiplicand in montgomery form 354 -> Montgomery -- ^ multiplier in montgomery form 355 -> Montgomery -- ^ montgomery product 356 mul (Montgomery a) (Montgomery b) = Montgomery (mul# a b) 357 358 to# 359 :: (# Limb, Limb, Limb, Limb #) -- ^ integer 360 -> (# Limb, Limb, Limb, Limb #) 361 to# x = 362 let -- r^2 mod m 363 !r2 = (# Limb 0x896CF21467D7D140##, Limb 0x741496C20E7CF878## 364 , Limb 0xE697F5E45BCD07C6##, Limb 0x9D671CD581C69BC5## #) 365 in mul# x r2 366 {-# INLINE to# #-} 367 368 -- | Convert a 'Wider' word to the Montgomery domain. 369 to_vartime :: Wider -> Montgomery 370 to_vartime (Wider x) = Montgomery (to# x) 371 372 -- | Retrieve a 'Montgomery' word from the Montgomery domain. 373 -- 374 -- This function is a synonym for 'retr'. 375 from_vartime :: Montgomery -> Wider 376 from_vartime = retr 377 378 add# 379 :: (# Limb, Limb, Limb, Limb #) -- ^ augend 380 -> (# Limb, Limb, Limb, Limb #) -- ^ addend 381 -> (# Limb, Limb, Limb, Limb #) -- ^ sum 382 add# a b = 383 let -- group order 384 !m = (# Limb 0xBFD25E8CD0364141##, Limb 0xBAAEDCE6AF48A03B## 385 , Limb 0xFFFFFFFFFFFFFFFE##, Limb 0xFFFFFFFFFFFFFFFF## #) 386 in WW.add_mod# a b m 387 {-# INLINE add# #-} 388 389 -- | Addition in the Montgomery domain. 390 -- 391 -- Note that 'Montgomery' is an instance of 'Num', so you can use '+' 392 -- to apply this function. 393 -- 394 -- >>> 1 + 1 :: Montgomery 395 -- 2 396 add 397 :: Montgomery -- ^ augend 398 -> Montgomery -- ^ addend 399 -> Montgomery -- ^ sum 400 add (Montgomery a) (Montgomery b) = Montgomery (add# a b) 401 402 sub# 403 :: (# Limb, Limb, Limb, Limb #) -- ^ minuend 404 -> (# Limb, Limb, Limb, Limb #) -- ^ subtrahend 405 -> (# Limb, Limb, Limb, Limb #) -- ^ difference 406 sub# a b = 407 let !m = (# Limb 0xBFD25E8CD0364141##, Limb 0xBAAEDCE6AF48A03B## 408 , Limb 0xFFFFFFFFFFFFFFFE##, Limb 0xFFFFFFFFFFFFFFFF## #) 409 in WW.sub_mod# a b m 410 {-# INLINE sub# #-} 411 412 -- | Subtraction in the Montgomery domain. 413 -- 414 -- Note that 'Montgomery' is an instance of 'Num', so you can use '-' 415 -- to apply this function. 416 -- 417 -- >>> 1 - 1 :: Montgomery 418 -- 0 419 sub 420 :: Montgomery -- ^ minuend 421 -> Montgomery -- ^ subtrahend 422 -> Montgomery -- ^ difference 423 sub (Montgomery a) (Montgomery b) = Montgomery (sub# a b) 424 425 neg# 426 :: (# Limb, Limb, Limb, Limb #) -- ^ argument 427 -> (# Limb, Limb, Limb, Limb #) -- ^ modular negation 428 neg# a = sub# (# Limb 0##, Limb 0##, Limb 0##, Limb 0## #) a 429 {-# INLINE neg# #-} 430 431 -- | Additive inverse in the Montgomery domain. 432 -- 433 -- Note that 'Montgomery' is an instance of 'Num', so you can use 'negate' 434 -- to apply this function. 435 -- 436 -- >>> negate 1 :: Montgomery 437 -- 115792089237316195423570985008687907852837564279074904382605163141518161494336 438 -- >>> (negate 1 :: Montgomery) + 1 439 -- 0 440 neg :: Montgomery -> Montgomery 441 neg (Montgomery a) = Montgomery (neg# a) 442 443 sqr# :: (# Limb, Limb, Limb, Limb #) -> (# Limb, Limb, Limb, Limb #) 444 sqr# a = 445 let !(# l, h #) = WW.sqr# a 446 in redc# l h 447 {-# NOINLINE sqr# #-} -- cannot be inlined without exploding comp time 448 449 -- | Squaring in the Montgomery domain. 450 -- 451 -- >>> sqr 1 452 -- 1 453 -- >>> sqr 2 454 -- 4 455 -- >>> sqr (negate 2) 456 -- 4 457 sqr 458 :: Montgomery -- ^ argument 459 -> Montgomery -- ^ square 460 sqr (Montgomery a) = Montgomery (mul# a a) 461 462 -- | Zero (the additive unit) in the Montgomery domain. 463 zero :: Montgomery 464 zero = Montgomery (# Limb 0##, Limb 0##, Limb 0##, Limb 0## #) 465 466 -- | One (the multiplicative unit) in the Montgomery domain. 467 one :: Montgomery 468 one = Montgomery 469 (# Limb 0x402DA1732FC9BEBF##, Limb 0x4551231950B75FC4## 470 , Limb 0x0000000000000001##, Limb 0x0000000000000000## #) 471 472 -- generated by etc/generate_inv.sh 473 inv# 474 :: (# Limb, Limb, Limb, Limb #) 475 -> (# Limb, Limb, Limb, Limb #) 476 inv# a = 477 let !t0 = (# Limb 0x402DA1732FC9BEBF##, Limb 0x4551231950B75FC4## 478 , Limb 0x0000000000000001##, Limb 0x0000000000000000## #) 479 !t1 = sqr# t0 480 !t2 = mul# a t1 481 !t3 = sqr# t2 482 !t4 = mul# a t3 483 !t5 = sqr# t4 484 !t6 = mul# a t5 485 !t7 = sqr# t6 486 !t8 = mul# a t7 487 !t9 = sqr# t8 488 !t10 = mul# a t9 489 !t11 = sqr# t10 490 !t12 = mul# a t11 491 !t13 = sqr# t12 492 !t14 = mul# a t13 493 !t15 = sqr# t14 494 !t16 = mul# a t15 495 !t17 = sqr# t16 496 !t18 = mul# a t17 497 !t19 = sqr# t18 498 !t20 = mul# a t19 499 !t21 = sqr# t20 500 !t22 = mul# a t21 501 !t23 = sqr# t22 502 !t24 = mul# a t23 503 !t25 = sqr# t24 504 !t26 = mul# a t25 505 !t27 = sqr# t26 506 !t28 = mul# a t27 507 !t29 = sqr# t28 508 !t30 = mul# a t29 509 !t31 = sqr# t30 510 !t32 = mul# a t31 511 !t33 = sqr# t32 512 !t34 = mul# a t33 513 !t35 = sqr# t34 514 !t36 = mul# a t35 515 !t37 = sqr# t36 516 !t38 = mul# a t37 517 !t39 = sqr# t38 518 !t40 = mul# a t39 519 !t41 = sqr# t40 520 !t42 = mul# a t41 521 !t43 = sqr# t42 522 !t44 = mul# a t43 523 !t45 = sqr# t44 524 !t46 = mul# a t45 525 !t47 = sqr# t46 526 !t48 = mul# a t47 527 !t49 = sqr# t48 528 !t50 = mul# a t49 529 !t51 = sqr# t50 530 !t52 = mul# a t51 531 !t53 = sqr# t52 532 !t54 = mul# a t53 533 !t55 = sqr# t54 534 !t56 = mul# a t55 535 !t57 = sqr# t56 536 !t58 = mul# a t57 537 !t59 = sqr# t58 538 !t60 = mul# a t59 539 !t61 = sqr# t60 540 !t62 = mul# a t61 541 !t63 = sqr# t62 542 !t64 = mul# a t63 543 !t65 = sqr# t64 544 !t66 = mul# a t65 545 !t67 = sqr# t66 546 !t68 = mul# a t67 547 !t69 = sqr# t68 548 !t70 = mul# a t69 549 !t71 = sqr# t70 550 !t72 = mul# a t71 551 !t73 = sqr# t72 552 !t74 = mul# a t73 553 !t75 = sqr# t74 554 !t76 = mul# a t75 555 !t77 = sqr# t76 556 !t78 = mul# a t77 557 !t79 = sqr# t78 558 !t80 = mul# a t79 559 !t81 = sqr# t80 560 !t82 = mul# a t81 561 !t83 = sqr# t82 562 !t84 = mul# a t83 563 !t85 = sqr# t84 564 !t86 = mul# a t85 565 !t87 = sqr# t86 566 !t88 = mul# a t87 567 !t89 = sqr# t88 568 !t90 = mul# a t89 569 !t91 = sqr# t90 570 !t92 = mul# a t91 571 !t93 = sqr# t92 572 !t94 = mul# a t93 573 !t95 = sqr# t94 574 !t96 = mul# a t95 575 !t97 = sqr# t96 576 !t98 = mul# a t97 577 !t99 = sqr# t98 578 !t100 = mul# a t99 579 !t101 = sqr# t100 580 !t102 = mul# a t101 581 !t103 = sqr# t102 582 !t104 = mul# a t103 583 !t105 = sqr# t104 584 !t106 = mul# a t105 585 !t107 = sqr# t106 586 !t108 = mul# a t107 587 !t109 = sqr# t108 588 !t110 = mul# a t109 589 !t111 = sqr# t110 590 !t112 = mul# a t111 591 !t113 = sqr# t112 592 !t114 = mul# a t113 593 !t115 = sqr# t114 594 !t116 = mul# a t115 595 !t117 = sqr# t116 596 !t118 = mul# a t117 597 !t119 = sqr# t118 598 !t120 = mul# a t119 599 !t121 = sqr# t120 600 !t122 = mul# a t121 601 !t123 = sqr# t122 602 !t124 = mul# a t123 603 !t125 = sqr# t124 604 !t126 = mul# a t125 605 !t127 = sqr# t126 606 !t128 = mul# a t127 607 !t129 = sqr# t128 608 !t130 = mul# a t129 609 !t131 = sqr# t130 610 !t132 = mul# a t131 611 !t133 = sqr# t132 612 !t134 = mul# a t133 613 !t135 = sqr# t134 614 !t136 = mul# a t135 615 !t137 = sqr# t136 616 !t138 = mul# a t137 617 !t139 = sqr# t138 618 !t140 = mul# a t139 619 !t141 = sqr# t140 620 !t142 = mul# a t141 621 !t143 = sqr# t142 622 !t144 = mul# a t143 623 !t145 = sqr# t144 624 !t146 = mul# a t145 625 !t147 = sqr# t146 626 !t148 = mul# a t147 627 !t149 = sqr# t148 628 !t150 = mul# a t149 629 !t151 = sqr# t150 630 !t152 = mul# a t151 631 !t153 = sqr# t152 632 !t154 = mul# a t153 633 !t155 = sqr# t154 634 !t156 = mul# a t155 635 !t157 = sqr# t156 636 !t158 = mul# a t157 637 !t159 = sqr# t158 638 !t160 = mul# a t159 639 !t161 = sqr# t160 640 !t162 = mul# a t161 641 !t163 = sqr# t162 642 !t164 = mul# a t163 643 !t165 = sqr# t164 644 !t166 = mul# a t165 645 !t167 = sqr# t166 646 !t168 = mul# a t167 647 !t169 = sqr# t168 648 !t170 = mul# a t169 649 !t171 = sqr# t170 650 !t172 = mul# a t171 651 !t173 = sqr# t172 652 !t174 = mul# a t173 653 !t175 = sqr# t174 654 !t176 = mul# a t175 655 !t177 = sqr# t176 656 !t178 = mul# a t177 657 !t179 = sqr# t178 658 !t180 = mul# a t179 659 !t181 = sqr# t180 660 !t182 = mul# a t181 661 !t183 = sqr# t182 662 !t184 = mul# a t183 663 !t185 = sqr# t184 664 !t186 = mul# a t185 665 !t187 = sqr# t186 666 !t188 = mul# a t187 667 !t189 = sqr# t188 668 !t190 = mul# a t189 669 !t191 = sqr# t190 670 !t192 = mul# a t191 671 !t193 = sqr# t192 672 !t194 = mul# a t193 673 !t195 = sqr# t194 674 !t196 = mul# a t195 675 !t197 = sqr# t196 676 !t198 = mul# a t197 677 !t199 = sqr# t198 678 !t200 = mul# a t199 679 !t201 = sqr# t200 680 !t202 = mul# a t201 681 !t203 = sqr# t202 682 !t204 = mul# a t203 683 !t205 = sqr# t204 684 !t206 = mul# a t205 685 !t207 = sqr# t206 686 !t208 = mul# a t207 687 !t209 = sqr# t208 688 !t210 = mul# a t209 689 !t211 = sqr# t210 690 !t212 = mul# a t211 691 !t213 = sqr# t212 692 !t214 = mul# a t213 693 !t215 = sqr# t214 694 !t216 = mul# a t215 695 !t217 = sqr# t216 696 !t218 = mul# a t217 697 !t219 = sqr# t218 698 !t220 = mul# a t219 699 !t221 = sqr# t220 700 !t222 = mul# a t221 701 !t223 = sqr# t222 702 !t224 = mul# a t223 703 !t225 = sqr# t224 704 !t226 = mul# a t225 705 !t227 = sqr# t226 706 !t228 = mul# a t227 707 !t229 = sqr# t228 708 !t230 = mul# a t229 709 !t231 = sqr# t230 710 !t232 = mul# a t231 711 !t233 = sqr# t232 712 !t234 = mul# a t233 713 !t235 = sqr# t234 714 !t236 = mul# a t235 715 !t237 = sqr# t236 716 !t238 = mul# a t237 717 !t239 = sqr# t238 718 !t240 = mul# a t239 719 !t241 = sqr# t240 720 !t242 = mul# a t241 721 !t243 = sqr# t242 722 !t244 = mul# a t243 723 !t245 = sqr# t244 724 !t246 = mul# a t245 725 !t247 = sqr# t246 726 !t248 = mul# a t247 727 !t249 = sqr# t248 728 !t250 = mul# a t249 729 !t251 = sqr# t250 730 !t252 = mul# a t251 731 !t253 = sqr# t252 732 !t254 = mul# a t253 733 !t255 = sqr# t254 734 !t256 = sqr# t255 735 !t257 = mul# a t256 736 !t258 = sqr# t257 737 !t259 = sqr# t258 738 !t260 = mul# a t259 739 !t261 = sqr# t260 740 !t262 = mul# a t261 741 !t263 = sqr# t262 742 !t264 = mul# a t263 743 !t265 = sqr# t264 744 !t266 = sqr# t265 745 !t267 = mul# a t266 746 !t268 = sqr# t267 747 !t269 = sqr# t268 748 !t270 = mul# a t269 749 !t271 = sqr# t270 750 !t272 = sqr# t271 751 !t273 = mul# a t272 752 !t274 = sqr# t273 753 !t275 = sqr# t274 754 !t276 = mul# a t275 755 !t277 = sqr# t276 756 !t278 = mul# a t277 757 !t279 = sqr# t278 758 !t280 = mul# a t279 759 !t281 = sqr# t280 760 !t282 = sqr# t281 761 !t283 = mul# a t282 762 !t284 = sqr# t283 763 !t285 = mul# a t284 764 !t286 = sqr# t285 765 !t287 = sqr# t286 766 !t288 = mul# a t287 767 !t289 = sqr# t288 768 !t290 = mul# a t289 769 !t291 = sqr# t290 770 !t292 = mul# a t291 771 !t293 = sqr# t292 772 !t294 = sqr# t293 773 !t295 = sqr# t294 774 !t296 = mul# a t295 775 !t297 = sqr# t296 776 !t298 = mul# a t297 777 !t299 = sqr# t298 778 !t300 = mul# a t299 779 !t301 = sqr# t300 780 !t302 = sqr# t301 781 !t303 = sqr# t302 782 !t304 = mul# a t303 783 !t305 = sqr# t304 784 !t306 = mul# a t305 785 !t307 = sqr# t306 786 !t308 = sqr# t307 787 !t309 = mul# a t308 788 !t310 = sqr# t309 789 !t311 = sqr# t310 790 !t312 = mul# a t311 791 !t313 = sqr# t312 792 !t314 = sqr# t313 793 !t315 = mul# a t314 794 !t316 = sqr# t315 795 !t317 = mul# a t316 796 !t318 = sqr# t317 797 !t319 = mul# a t318 798 !t320 = sqr# t319 799 !t321 = mul# a t320 800 !t322 = sqr# t321 801 !t323 = sqr# t322 802 !t324 = mul# a t323 803 !t325 = sqr# t324 804 !t326 = sqr# t325 805 !t327 = sqr# t326 806 !t328 = mul# a t327 807 !t329 = sqr# t328 808 !t330 = sqr# t329 809 !t331 = sqr# t330 810 !t332 = sqr# t331 811 !t333 = mul# a t332 812 !t334 = sqr# t333 813 !t335 = sqr# t334 814 !t336 = mul# a t335 815 !t337 = sqr# t336 816 !t338 = sqr# t337 817 !t339 = sqr# t338 818 !t340 = sqr# t339 819 !t341 = sqr# t340 820 !t342 = sqr# t341 821 !t343 = sqr# t342 822 !t344 = sqr# t343 823 !t345 = mul# a t344 824 !t346 = sqr# t345 825 !t347 = mul# a t346 826 !t348 = sqr# t347 827 !t349 = mul# a t348 828 !t350 = sqr# t349 829 !t351 = sqr# t350 830 !t352 = mul# a t351 831 !t353 = sqr# t352 832 !t354 = mul# a t353 833 !t355 = sqr# t354 834 !t356 = mul# a t355 835 !t357 = sqr# t356 836 !t358 = sqr# t357 837 !t359 = mul# a t358 838 !t360 = sqr# t359 839 !t361 = mul# a t360 840 !t362 = sqr# t361 841 !t363 = mul# a t362 842 !t364 = sqr# t363 843 !t365 = mul# a t364 844 !t366 = sqr# t365 845 !t367 = mul# a t366 846 !t368 = sqr# t367 847 !t369 = mul# a t368 848 !t370 = sqr# t369 849 !t371 = mul# a t370 850 !t372 = sqr# t371 851 !t373 = mul# a t372 852 !t374 = sqr# t373 853 !t375 = sqr# t374 854 !t376 = mul# a t375 855 !t377 = sqr# t376 856 !t378 = sqr# t377 857 !t379 = sqr# t378 858 !t380 = mul# a t379 859 !t381 = sqr# t380 860 !t382 = sqr# t381 861 !t383 = sqr# t382 862 !t384 = mul# a t383 863 !t385 = sqr# t384 864 !t386 = sqr# t385 865 !t387 = mul# a t386 866 !t388 = sqr# t387 867 !t389 = mul# a t388 868 !t390 = sqr# t389 869 !t391 = mul# a t390 870 !t392 = sqr# t391 871 !t393 = mul# a t392 872 !t394 = sqr# t393 873 !t395 = sqr# t394 874 !t396 = mul# a t395 875 !t397 = sqr# t396 876 !t398 = sqr# t397 877 !t399 = sqr# t398 878 !t400 = sqr# t399 879 !t401 = mul# a t400 880 !t402 = sqr# t401 881 !t403 = mul# a t402 882 !t404 = sqr# t403 883 !t405 = sqr# t404 884 !t406 = sqr# t405 885 !t407 = mul# a t406 886 !t408 = sqr# t407 887 !t409 = mul# a t408 888 !t410 = sqr# t409 889 !t411 = sqr# t410 890 !t412 = mul# a t411 891 !t413 = sqr# t412 892 !t414 = sqr# t413 893 !t415 = sqr# t414 894 !t416 = sqr# t415 895 !t417 = sqr# t416 896 !t418 = sqr# t417 897 !t419 = sqr# t418 898 !t420 = mul# a t419 899 !t421 = sqr# t420 900 !t422 = mul# a t421 901 !t423 = sqr# t422 902 !t424 = sqr# t423 903 !t425 = mul# a t424 904 !t426 = sqr# t425 905 !t427 = mul# a t426 906 !t428 = sqr# t427 907 !t429 = sqr# t428 908 !t430 = sqr# t429 909 !t431 = mul# a t430 910 !t432 = sqr# t431 911 !t433 = sqr# t432 912 !t434 = sqr# t433 913 !t435 = sqr# t434 914 !t436 = sqr# t435 915 !t437 = sqr# t436 916 !t438 = mul# a t437 917 !t439 = sqr# t438 918 !t440 = sqr# t439 919 !t441 = sqr# t440 920 !t442 = mul# a t441 921 !t443 = sqr# t442 922 !t444 = mul# a t443 923 !t445 = sqr# t444 924 !t446 = mul# a t445 925 !t447 = sqr# t446 926 !t448 = mul# a t447 927 !t449 = sqr# t448 928 !t450 = mul# a t449 929 !t451 = sqr# t450 930 !t452 = mul# a t451 931 !r = t452 932 in r 933 {-# INLINE inv# #-} 934 935 -- | Multiplicative inverse in the Montgomery domain. 936 -- 937 -- >> inv 2 938 -- 57896044618658097711785492504343953926418782139537452191302581570759080747169 939 -- >> inv 2 * 2 940 -- 1 941 inv 942 :: Montgomery -- ^ argument 943 -> Montgomery -- ^ inverse 944 inv (Montgomery w) = Montgomery (inv# w) 945 946 -- | Exponentiation in the Montgomery domain. 947 -- 948 -- >>> exp 2 3 949 -- 8 950 -- >>> exp 2 10 951 -- 1024 952 exp :: Montgomery -> Wider -> Montgomery 953 exp (Montgomery b) (Wider e) = 954 let !one# = (# Limb 0x402DA1732FC9BEBF##, Limb 0x4551231950B75FC4## 955 , Limb 0x0000000000000001##, Limb 0x0000000000000000## #) 956 loop !r !_ !_ 0 = r 957 loop !r !m !ex !n = 958 let !(# ne, bit #) = WW.shr1_c# ex 959 !candidate = mul# r m 960 !nr = select# r candidate bit 961 !nm = sqr# m 962 in loop nr nm ne (n - 1) 963 in Montgomery (loop one# b e (256 :: Word)) 964 965 odd# :: (# Limb, Limb, Limb, Limb #) -> C.Choice 966 odd# = WW.odd# 967 {-# INLINE odd# #-} 968 969 -- | Check if a 'Montgomery' value is odd. 970 -- 971 -- Note that the comparison is performed in constant time, but we 972 -- branch when converting to 'Bool'. 973 -- 974 -- >>> odd 1 975 -- True 976 -- >>> odd 2 977 -- False 978 -- >>> Data.Word.Wider.odd (retr 3) -- parity is preserved 979 -- True 980 odd_vartime :: Montgomery -> Bool 981 odd_vartime (Montgomery m) = C.decide (odd# m) 982 983 -- constant-time selection ---------------------------------------------------- 984 985 select# 986 :: (# Limb, Limb, Limb, Limb #) -- ^ a 987 -> (# Limb, Limb, Limb, Limb #) -- ^ b 988 -> C.Choice -- ^ c 989 -> (# Limb, Limb, Limb, Limb #) -- ^ result 990 select# = WW.select# 991 {-# INLINE select# #-} 992 993 -- | Return a if c is truthy, otherwise return b. 994 -- 995 -- >>> import qualified Data.Choice as C 996 -- >>> select 0 1 (C.true# ()) 997 -- 1 998 select 999 :: Montgomery -- ^ a 1000 -> Montgomery -- ^ b 1001 -> C.Choice -- ^ c 1002 -> Montgomery -- ^ result 1003 select (Montgomery a) (Montgomery b) c = Montgomery (select# a b c) 1004