Curve.hs (37926B)
1 {-# LANGUAGE BangPatterns #-} 2 {-# LANGUAGE MagicHash #-} 3 {-# LANGUAGE NumericUnderscores #-} 4 {-# LANGUAGE PatternSynonyms #-} 5 {-# LANGUAGE ViewPatterns #-} 6 {-# LANGUAGE UnboxedSums #-} 7 {-# LANGUAGE UnboxedTuples #-} 8 {-# LANGUAGE UnliftedNewtypes #-} 9 10 -- | 11 -- Module: Numeric.Montgomery.Secp256k1.Curve 12 -- Copyright: (c) 2025 Jared Tobin 13 -- License: MIT 14 -- Maintainer: Jared Tobin <jared@ppad.tech> 15 -- 16 -- Montgomery form 'Wider' words, as well as arithmetic operations, with 17 -- domain derived from the secp256k1 elliptic curve field prime. 18 19 module Numeric.Montgomery.Secp256k1.Curve ( 20 -- * Montgomery form, secp256k1 field prime modulus 21 Montgomery(..) 22 , render 23 , to 24 , from 25 , zero 26 , one 27 28 -- * Comparison 29 , eq 30 , eq_vartime 31 32 -- * Reduction and retrieval 33 , redc 34 , redc# 35 , retr 36 , retr# 37 38 -- * Constant-time selection 39 , select 40 , select# 41 42 -- * Montgomery arithmetic 43 , add 44 , add# 45 , sub 46 , sub# 47 , mul 48 , mul# 49 , sqr 50 , sqr# 51 , neg 52 , neg# 53 , inv 54 , inv# 55 , sqrt_vartime 56 , sqrt# 57 , exp 58 , exp# 59 , odd# 60 , odd_vartime 61 ) where 62 63 import Control.DeepSeq 64 import qualified Data.Choice as C 65 import Data.Word.Limb (Limb(..)) 66 import qualified Data.Word.Limb as L 67 import qualified Data.Word.Wide as W 68 import Data.Word.Wider (Wider(..)) 69 import qualified Data.Word.Wider as WW 70 import GHC.Exts (Word(..), Word#) 71 import Prelude hiding (or, and, not, sqrt, exp) 72 73 -- montgomery arithmetic, specialized to the secp256k1 field prime modulus 74 -- 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F 75 76 -- | Montgomery-form 'Wider' words, on the Montgomery domain defined by 77 -- the secp256k1 field prime. 78 -- 79 -- >>> let one = 1 :: Montgomery 80 -- >>> one 81 -- 1 82 -- >>> putStrLn (render one) 83 -- (4294968273, 0, 0, 0) 84 data Montgomery = Montgomery !Limb4 85 86 -- | Render a 'Montgomery' value as a 'String', showing its individual 87 -- 'Limb's. 88 -- 89 -- >>> putStrLn (render 1) 90 -- (4294968273, 0, 0, 0) 91 render :: Montgomery -> String 92 render (Montgomery (L4 a b c d)) = 93 "(" <> show (W# a) <> ", " <> show (W# b) <> ", " 94 <> show (W# c) <> ", " <> show (W# d) <> ")" 95 96 instance Show Montgomery where 97 show = show . from 98 99 -- | Note that 'fromInteger' necessarily runs in variable time due 100 -- to conversion from the variable-size, potentially heap-allocated 101 -- 'Integer' type. 102 instance Num Montgomery where 103 a + b = add a b 104 a - b = sub a b 105 a * b = mul a b 106 negate a = neg a 107 abs = id 108 fromInteger = to . WW.to_vartime 109 signum (Montgomery (# l0, l1, l2, l3 #)) = 110 let !(Limb l) = l0 `L.or#` l1 `L.or#` l2 `L.or#` l3 111 !n = C.from_word_nonzero# l 112 !(Montgomery z) = zero 113 !(Montgomery o) = one 114 in Montgomery (select# z o n) 115 116 instance NFData Montgomery where 117 rnf (Montgomery a) = case a of (# _, _, _, _ #) -> () 118 119 -- utilities ------------------------------------------------------------------ 120 121 type Limb2 = (# Limb, Limb #) 122 123 type Limb4 = (# Limb, Limb, Limb, Limb #) 124 125 pattern L4 :: Word# -> Word# -> Word# -> Word# -> Limb4 126 pattern L4 w0 w1 w2 w3 = (# Limb w0, Limb w1, Limb w2, Limb w3 #) 127 {-# COMPLETE L4 #-} 128 129 -- Wide wrapping addition, when addend is only a limb. 130 wadd_w# :: Limb2 -> Limb -> Limb2 131 wadd_w# (# x_lo, x_hi #) y_lo = 132 let !(# s0, c0 #) = L.add_o# x_lo y_lo 133 !(# s1, _ #) = L.add_o# x_hi c0 134 in (# s0, s1 #) 135 {-# INLINE wadd_w# #-} 136 137 -- Truncate a wide word to a 'Limb'. 138 lo :: Limb2 -> Limb 139 lo (# l, _ #) = l 140 {-# INLINE lo #-} 141 142 -- comparison ----------------------------------------------------------------- 143 144 -- | Constant-time equality comparison. 145 eq :: Montgomery -> Montgomery -> C.Choice 146 eq (Montgomery (L4 a0 a1 a2 a3)) (Montgomery (L4 b0 b1 b2 b3)) = 147 C.eq_wider# (# a0, a1, a2, a3 #) (# b0, b1, b2, b3 #) 148 {-# INLINE eq #-} 149 150 -- | Variable-time equality comparison. 151 eq_vartime :: Montgomery -> Montgomery -> Bool 152 eq_vartime (Montgomery (Wider -> a)) (Montgomery (Wider -> b)) = 153 WW.eq_vartime a b 154 155 -- innards -------------------------------------------------------------------- 156 157 redc_inner# 158 :: Limb4 -- ^ upper limbs 159 -> Limb4 -- ^ lower limbs 160 -> (# Limb4, Limb #) -- ^ upper limbs, meta-carry 161 redc_inner# (# u0, u1, u2, u3 #) (# l0, l1, l2, l3 #) = 162 let !(# m0, m1, m2, m3 #) = 163 (# Limb 0xFFFFFFFEFFFFFC2F##, Limb 0xFFFFFFFFFFFFFFFF## 164 , Limb 0xFFFFFFFFFFFFFFFF##, Limb 0xFFFFFFFFFFFFFFFF## #) 165 !n = Limb 0xD838091DD2253531## 166 !w_0 = L.mul_w# l0 n 167 !(# _, c_00 #) = L.mac# w_0 m0 l0 (Limb 0##) 168 !(# l0_1, c_01 #) = L.mac# w_0 m1 l1 c_00 169 !(# l0_2, c_02 #) = L.mac# w_0 m2 l2 c_01 170 !(# l0_3, c_03 #) = L.mac# w_0 m3 l3 c_02 171 !(# u_0, mc_0 #) = L.add_c# u0 c_03 (Limb 0##) 172 !w_1 = L.mul_w# l0_1 n 173 !(# _, c_10 #) = L.mac# w_1 m0 l0_1 (Limb 0##) 174 !(# l1_1, c_11 #) = L.mac# w_1 m1 l0_2 c_10 175 !(# l1_2, c_12 #) = L.mac# w_1 m2 l0_3 c_11 176 !(# u1_3, c_13 #) = L.mac# w_1 m3 u_0 c_12 177 !(# u_1, mc_1 #) = L.add_c# u1 c_13 mc_0 178 !w_2 = L.mul_w# l1_1 n 179 !(# _, c_20 #) = L.mac# w_2 m0 l1_1 (Limb 0##) 180 !(# l2_1, c_21 #) = L.mac# w_2 m1 l1_2 c_20 181 !(# u2_2, c_22 #) = L.mac# w_2 m2 u1_3 c_21 182 !(# u2_3, c_23 #) = L.mac# w_2 m3 u_1 c_22 183 !(# u_2, mc_2 #) = L.add_c# u2 c_23 mc_1 184 !w_3 = L.mul_w# l2_1 n 185 !(# _, c_30 #) = L.mac# w_3 m0 l2_1 (Limb 0##) 186 !(# u3_1, c_31 #) = L.mac# w_3 m1 u2_2 c_30 187 !(# u3_2, c_32 #) = L.mac# w_3 m2 u2_3 c_31 188 !(# u3_3, c_33 #) = L.mac# w_3 m3 u_2 c_32 189 !(# u_3, mc_3 #) = L.add_c# u3 c_33 mc_2 190 in (# (# u3_1, u3_2, u3_3, u_3 #), mc_3 #) 191 {-# INLINE redc_inner# #-} 192 193 -- | Montgomery reduction. 194 redc# 195 :: Limb4 -- ^ lower limbs 196 -> Limb4 -- ^ upper limbs 197 -> Limb4 -- ^ result 198 redc# l u = 199 let -- field prime 200 !m = L4 0xFFFFFFFEFFFFFC2F## 0xFFFFFFFFFFFFFFFF## 201 0xFFFFFFFFFFFFFFFF## 0xFFFFFFFFFFFFFFFF## 202 !(# nu, mc #) = redc_inner# u l 203 in WW.sub_mod_c# nu mc m m 204 {-# INLINE redc# #-} 205 206 -- | Montgomery reduction. 207 -- 208 -- The first argument represents the low words, and the second the 209 -- high words, of an extra-large eight-limb word in Montgomery form. 210 redc 211 :: Montgomery -- ^ low wider-word, Montgomery form 212 -> Montgomery -- ^ high wider-word, Montgomery form 213 -> Montgomery -- ^ reduced value 214 redc (Montgomery l) (Montgomery u) = 215 let !res = redc# l u 216 in Montgomery res 217 218 retr_inner# 219 :: Limb4 -- ^ value in montgomery form 220 -> Limb4 -- ^ retrieved value 221 retr_inner# (# x0, x1, x2, x3 #) = 222 let !(# m0, m1, m2, m3 #) = 223 L4 0xFFFFFFFEFFFFFC2F## 0xFFFFFFFFFFFFFFFF## 224 0xFFFFFFFFFFFFFFFF## 0xFFFFFFFFFFFFFFFF## 225 !n = Limb 0xD838091DD2253531## 226 !u_0 = L.mul_w# x0 n 227 !(# _, o0 #) = L.mac# u_0 m0 x0 (Limb 0##) 228 !(# o0_1, p0_1 #) = L.mac# u_0 m1 (Limb 0##) o0 229 !(# p0_2, q0_2 #) = L.mac# u_0 m2 (Limb 0##) p0_1 230 !(# q0_3, r0_3 #) = L.mac# u_0 m3 (Limb 0##) q0_2 231 !u_1 = L.mul_w# (L.add_w# o0_1 x1) n 232 !(# _, o1 #) = L.mac# u_1 m0 x1 o0_1 233 !(# o1_1, p1_1 #) = L.mac# u_1 m1 p0_2 o1 234 !(# p1_2, q1_2 #) = L.mac# u_1 m2 q0_3 p1_1 235 !(# q1_3, r1_3 #) = L.mac# u_1 m3 r0_3 q1_2 236 !u_2 = L.mul_w# (L.add_w# o1_1 x2) n 237 !(# _, o2 #) = L.mac# u_2 m0 x2 o1_1 238 !(# o2_1, p2_1 #) = L.mac# u_2 m1 p1_2 o2 239 !(# p2_2, q2_2 #) = L.mac# u_2 m2 q1_3 p2_1 240 !(# q2_3, r2_3 #) = L.mac# u_2 m3 r1_3 q2_2 241 !u_3 = L.mul_w# (L.add_w# o2_1 x3) n 242 !(# _, o3 #) = L.mac# u_3 m0 x3 o2_1 243 !(# o3_1, p3_1 #) = L.mac# u_3 m1 p2_2 o3 244 !(# p3_2, q3_2 #) = L.mac# u_3 m2 q2_3 p3_1 245 !(# q3_3, r3_3 #) = L.mac# u_3 m3 r2_3 q3_2 246 in (# o3_1, p3_2, q3_3, r3_3 #) 247 {-# INLINE retr_inner# #-} 248 249 retr# 250 :: Limb4 -- montgomery form 251 -> Limb4 252 retr# f = retr_inner# f 253 {-# INLINE retr# #-} 254 255 -- | Retrieve a 'Montgomery' value from the Montgomery domain, producing 256 -- a 'Wider' word. 257 retr 258 :: Montgomery -- ^ value in montgomery form 259 -> Wider -- ^ retrieved value 260 retr (Montgomery f) = 261 let !res = retr# f 262 in (Wider res) 263 264 -- | Montgomery multiplication (FIOS), without conditional subtract. 265 mul_inner# 266 :: Limb4 -- ^ x 267 -> Limb4 -- ^ y 268 -> (# Limb4, Limb #) -- ^ product, meta-carry 269 mul_inner# (# x0, x1, x2, x3 #) (# y0, y1, y2, y3 #) = 270 let !(# m0, m1, m2, m3 #) = 271 L4 0xFFFFFFFEFFFFFC2F## 0xFFFFFFFFFFFFFFFF## 272 0xFFFFFFFFFFFFFFFF## 0xFFFFFFFFFFFFFFFF## 273 !n = Limb 0xD838091DD2253531## 274 !axy0 = L.mul_c# x0 y0 275 !u0 = L.mul_w# (lo axy0) n 276 !(# (# _, a0 #), c0 #) = W.add_o# (L.mul_c# u0 m0) axy0 277 !carry0 = (# a0, c0 #) 278 !axy0_1 = L.mul_c# x0 y1 279 !umc0_1 = W.add_w# (L.mul_c# u0 m1) carry0 280 !(# (# o0, ab0_1 #), c0_1 #) = W.add_o# axy0_1 umc0_1 281 !carry0_1 = (# ab0_1, c0_1 #) 282 !axy0_2 = L.mul_c# x0 y2 283 !umc0_2 = W.add_w# (L.mul_c# u0 m2) carry0_1 284 !(# (# p0, ab0_2 #), c0_2 #) = W.add_o# axy0_2 umc0_2 285 !carry0_2 = (# ab0_2, c0_2 #) 286 !axy0_3 = L.mul_c# x0 y3 287 !umc0_3 = W.add_w# (L.mul_c# u0 m3) carry0_2 288 !(# (# q0, ab0_3 #), c0_3 #) = W.add_o# axy0_3 umc0_3 289 !carry0_3 = (# ab0_3, c0_3 #) 290 !(# r0, mc0 #) = carry0_3 291 !axy1 = wadd_w# (L.mul_c# x1 y0) o0 292 !u1 = L.mul_w# (lo axy1) n 293 !(# (# _, a1 #), c1 #) = W.add_o# (L.mul_c# u1 m0) axy1 294 !carry1 = (# a1, c1 #) 295 !axy1_1 = wadd_w# (L.mul_c# x1 y1) p0 296 !umc1_1 = W.add_w# (L.mul_c# u1 m1) carry1 297 !(# (# o1, ab1_1 #), c1_1 #) = W.add_o# axy1_1 umc1_1 298 !carry1_1 = (# ab1_1, c1_1 #) 299 !axy1_2 = wadd_w# (L.mul_c# x1 y2) q0 300 !umc1_2 = W.add_w# (L.mul_c# u1 m2) carry1_1 301 !(# (# p1, ab1_2 #), c1_2 #) = W.add_o# axy1_2 umc1_2 302 !carry1_2 = (# ab1_2, c1_2 #) 303 !axy1_3 = wadd_w# (L.mul_c# x1 y3) r0 304 !umc1_3 = W.add_w# (L.mul_c# u1 m3) carry1_2 305 !(# (# q1, ab1_3 #), c1_3 #) = W.add_o# axy1_3 umc1_3 306 !carry1_3 = (# ab1_3, c1_3 #) 307 !(# r1, mc1 #) = wadd_w# carry1_3 mc0 308 !axy2 = wadd_w# (L.mul_c# x2 y0) o1 309 !u2 = L.mul_w# (lo axy2) n 310 !(# (# _, a2 #), c2 #) = W.add_o# (L.mul_c# u2 m0) axy2 311 !carry2 = (# a2, c2 #) 312 !axy2_1 = wadd_w# (L.mul_c# x2 y1) p1 313 !umc2_1 = W.add_w# (L.mul_c# u2 m1) carry2 314 !(# (# o2, ab2_1 #), c2_1 #) = W.add_o# axy2_1 umc2_1 315 !carry2_1 = (# ab2_1, c2_1 #) 316 !axy2_2 = wadd_w# (L.mul_c# x2 y2) q1 317 !umc2_2 = W.add_w# (L.mul_c# u2 m2) carry2_1 318 !(# (# p2, ab2_2 #), c2_2 #) = W.add_o# axy2_2 umc2_2 319 !carry2_2 = (# ab2_2, c2_2 #) 320 !axy2_3 = wadd_w# (L.mul_c# x2 y3) r1 321 !umc2_3 = W.add_w# (L.mul_c# u2 m3) carry2_2 322 !(# (# q2, ab2_3 #), c2_3 #) = W.add_o# axy2_3 umc2_3 323 !carry2_3 = (# ab2_3, c2_3 #) 324 !(# r2, mc2 #) = wadd_w# carry2_3 mc1 325 !axy3 = wadd_w# (L.mul_c# x3 y0) o2 326 !u3 = L.mul_w# (lo axy3) n 327 !(# (# _, a3 #), c3 #) = W.add_o# (L.mul_c# u3 m0) axy3 328 !carry3 = (# a3, c3 #) 329 !axy3_1 = wadd_w# (L.mul_c# x3 y1) p2 330 !umc3_1 = W.add_w# (L.mul_c# u3 m1) carry3 331 !(# (# o3, ab3_1 #), c3_1 #) = W.add_o# axy3_1 umc3_1 332 !carry3_1 = (# ab3_1, c3_1 #) 333 !axy3_2 = wadd_w# (L.mul_c# x3 y2) q2 334 !umc3_2 = W.add_w# (L.mul_c# u3 m2) carry3_1 335 !(# (# p3, ab3_2 #), c3_2 #) = W.add_o# axy3_2 umc3_2 336 !carry3_2 = (# ab3_2, c3_2 #) 337 !axy3_3 = wadd_w# (L.mul_c# x3 y3) r2 338 !umc3_3 = W.add_w# (L.mul_c# u3 m3) carry3_2 339 !(# (# q3, ab3_3 #), c3_3 #) = W.add_o# axy3_3 umc3_3 340 !carry3_3 = (# ab3_3, c3_3 #) 341 !(# r3, mc3 #) = wadd_w# carry3_3 mc2 342 in (# (# o3, p3, q3, r3 #), mc3 #) 343 {-# INLINE mul_inner# #-} 344 345 mul# 346 :: Limb4 347 -> Limb4 348 -> Limb4 349 mul# a b = 350 let -- field prime 351 !m = L4 0xFFFFFFFEFFFFFC2F## 0xFFFFFFFFFFFFFFFF## 352 0xFFFFFFFFFFFFFFFF## 0xFFFFFFFFFFFFFFFF## 353 !(# nu, mc #) = mul_inner# a b 354 in WW.sub_mod_c# nu mc m m 355 {-# NOINLINE mul# #-} -- cannot be inlined without exploding comp time 356 357 -- | Multiplication in the Montgomery domain. 358 -- 359 -- Note that 'Montgomery' is an instance of 'Num', so you can use '*' 360 -- to apply this function. 361 -- 362 -- >>> 1 * 1 :: Montgomery 363 -- 1 364 mul 365 :: Montgomery -- ^ multiplicand in montgomery form 366 -> Montgomery -- ^ multiplier in montgomery form 367 -> Montgomery -- ^ montgomery product 368 mul (Montgomery a) (Montgomery b) = Montgomery (mul# a b) 369 370 to# 371 :: Limb4 -- ^ integer 372 -> Limb4 373 to# x = 374 let !r2 = L4 0x000007A2000E90A1## 0x1## 0## 0## -- r^2 mod m 375 in mul# x r2 376 {-# INLINE to# #-} 377 378 -- | Convert a 'Wider' word to the Montgomery domain. 379 to :: Wider -> Montgomery 380 to (Wider x) = Montgomery (to# x) 381 382 -- | Retrieve a 'Montgomery' word from the Montgomery domain. 383 -- 384 -- This function is a synonym for 'retr'. 385 from :: Montgomery -> Wider 386 from = retr 387 388 add# 389 :: Limb4 -- ^ augend 390 -> Limb4 -- ^ addend 391 -> Limb4 -- ^ sum 392 add# a b = 393 let -- field prime 394 !m = L4 0xFFFFFFFEFFFFFC2F## 0xFFFFFFFFFFFFFFFF## 395 0xFFFFFFFFFFFFFFFF## 0xFFFFFFFFFFFFFFFF## 396 in WW.add_mod# a b m 397 {-# INLINE add# #-} 398 399 -- | Addition in the Montgomery domain. 400 -- 401 -- Note that 'Montgomery' is an instance of 'Num', so you can use '+' 402 -- to apply this function. 403 -- 404 -- >>> 1 + 1 :: Montgomery 405 -- 2 406 add :: Montgomery -> Montgomery -> Montgomery 407 add (Montgomery a) (Montgomery b) = Montgomery (add# a b) 408 409 sub# 410 :: Limb4 -- ^ minuend 411 -> Limb4 -- ^ subtrahend 412 -> Limb4 -- ^ difference 413 sub# a b = 414 let -- field prime 415 !m = L4 0xFFFFFFFEFFFFFC2F## 0xFFFFFFFFFFFFFFFF## 416 0xFFFFFFFFFFFFFFFF## 0xFFFFFFFFFFFFFFFF## 417 in WW.sub_mod# a b m 418 {-# INLINE sub# #-} 419 420 -- | Subtraction in the Montgomery domain. 421 -- 422 -- Note that 'Montgomery' is an instance of 'Num', so you can use '-' 423 -- to apply this function. 424 -- 425 -- >>> 1 - 1 :: Montgomery 426 -- 0 427 sub :: Montgomery -> Montgomery -> Montgomery 428 sub (Montgomery a) (Montgomery b) = Montgomery (sub# a b) 429 430 neg# 431 :: Limb4 -- ^ argument 432 -> Limb4 -- ^ modular negation 433 neg# a = sub# (L4 0## 0## 0## 0##) a 434 {-# INLINE neg# #-} 435 436 -- | Additive inverse in the Montgomery domain. 437 -- 438 -- Note that 'Montgomery' is an instance of 'Num', so you can use 'negate' 439 -- to apply this function. 440 -- 441 -- >>> negate 1 :: Montgomery 442 -- 115792089237316195423570985008687907853269984665640564039457584007908834671662 443 -- >>> (negate 1 :: Montgomery) + 1 444 -- 0 445 neg :: Montgomery -> Montgomery 446 neg (Montgomery a) = Montgomery (neg# a) 447 448 sqr# :: Limb4 -> Limb4 449 sqr# a = 450 let !(# l, h #) = WW.sqr# a 451 in redc# l h 452 {-# NOINLINE sqr# #-} -- cannot be inlined without exploding comp time 453 454 -- | Squaring in the Montgomery domain. 455 -- 456 -- >>> sqr 1 457 -- 1 458 -- >>> sqr 2 459 -- 4 460 -- >>> sqr (negate 2) 461 -- 4 462 sqr :: Montgomery -> Montgomery 463 sqr (Montgomery a) = Montgomery (mul# a a) 464 465 -- | Zero (the additive unit) in the Montgomery domain. 466 zero :: Montgomery 467 zero = Montgomery (L4 0## 0## 0## 0##) 468 469 -- | One (the multiplicative unit) in the Montgomery domain. 470 one :: Montgomery 471 one = Montgomery (L4 0x1000003D1## 0## 0## 0##) 472 473 -- generated by etc/generate_inv.sh 474 inv# 475 :: Limb4 476 -> Limb4 477 inv# a = 478 let 479 !t1 = sqr# a 480 !t2 = mul# t1 a 481 !t3 = sqr# t2 482 !t4 = sqr# t3 483 !t5 = mul# t4 t2 484 !t6 = sqr# t5 485 !t7 = sqr# t6 486 !t8 = sqr# t7 487 !t9 = sqr# t8 488 !t10 = mul# t9 t5 489 !t11 = sqr# t10 490 !t12 = sqr# t11 491 !t13 = sqr# t12 492 !t14 = sqr# t13 493 !t15 = sqr# t14 494 !t16 = sqr# t15 495 !t17 = sqr# t16 496 !t18 = sqr# t17 497 !t19 = mul# t18 t10 498 !t20 = sqr# t19 499 !t21 = sqr# t20 500 !t22 = sqr# t21 501 !t23 = sqr# t22 502 !t24 = sqr# t23 503 !t25 = sqr# t24 504 !t26 = sqr# t25 505 !t27 = sqr# t26 506 !t28 = sqr# t27 507 !t29 = sqr# t28 508 !t30 = sqr# t29 509 !t31 = sqr# t30 510 !t32 = sqr# t31 511 !t33 = sqr# t32 512 !t34 = sqr# t33 513 !t35 = sqr# t34 514 !t36 = mul# t35 t19 515 !t37 = sqr# t36 516 !t38 = sqr# t37 517 !t39 = sqr# t38 518 !t40 = sqr# t39 519 !t41 = sqr# t40 520 !t42 = sqr# t41 521 !t43 = sqr# t42 522 !t44 = sqr# t43 523 !t45 = sqr# t44 524 !t46 = sqr# t45 525 !t47 = sqr# t46 526 !t48 = sqr# t47 527 !t49 = sqr# t48 528 !t50 = sqr# t49 529 !t51 = sqr# t50 530 !t52 = sqr# t51 531 !t53 = sqr# t52 532 !t54 = sqr# t53 533 !t55 = sqr# t54 534 !t56 = sqr# t55 535 !t57 = sqr# t56 536 !t58 = sqr# t57 537 !t59 = sqr# t58 538 !t60 = sqr# t59 539 !t61 = sqr# t60 540 !t62 = sqr# t61 541 !t63 = sqr# t62 542 !t64 = sqr# t63 543 !t65 = sqr# t64 544 !t66 = sqr# t65 545 !t67 = sqr# t66 546 !t68 = sqr# t67 547 !t69 = mul# t68 t36 548 !t70 = sqr# t69 549 !t71 = sqr# t70 550 !t72 = sqr# t71 551 !t73 = sqr# t72 552 !t74 = sqr# t73 553 !t75 = sqr# t74 554 !t76 = sqr# t75 555 !t77 = sqr# t76 556 !t78 = sqr# t77 557 !t79 = sqr# t78 558 !t80 = sqr# t79 559 !t81 = sqr# t80 560 !t82 = sqr# t81 561 !t83 = sqr# t82 562 !t84 = sqr# t83 563 !t85 = sqr# t84 564 !t86 = sqr# t85 565 !t87 = sqr# t86 566 !t88 = sqr# t87 567 !t89 = sqr# t88 568 !t90 = sqr# t89 569 !t91 = sqr# t90 570 !t92 = sqr# t91 571 !t93 = sqr# t92 572 !t94 = sqr# t93 573 !t95 = sqr# t94 574 !t96 = sqr# t95 575 !t97 = sqr# t96 576 !t98 = sqr# t97 577 !t99 = sqr# t98 578 !t100 = sqr# t99 579 !t101 = sqr# t100 580 !t102 = sqr# t101 581 !t103 = sqr# t102 582 !t104 = sqr# t103 583 !t105 = sqr# t104 584 !t106 = sqr# t105 585 !t107 = sqr# t106 586 !t108 = sqr# t107 587 !t109 = sqr# t108 588 !t110 = sqr# t109 589 !t111 = sqr# t110 590 !t112 = sqr# t111 591 !t113 = sqr# t112 592 !t114 = sqr# t113 593 !t115 = sqr# t114 594 !t116 = sqr# t115 595 !t117 = sqr# t116 596 !t118 = sqr# t117 597 !t119 = sqr# t118 598 !t120 = sqr# t119 599 !t121 = sqr# t120 600 !t122 = sqr# t121 601 !t123 = sqr# t122 602 !t124 = sqr# t123 603 !t125 = sqr# t124 604 !t126 = sqr# t125 605 !t127 = sqr# t126 606 !t128 = sqr# t127 607 !t129 = sqr# t128 608 !t130 = sqr# t129 609 !t131 = sqr# t130 610 !t132 = sqr# t131 611 !t133 = sqr# t132 612 !t134 = mul# t133 t69 613 !t135 = sqr# t134 614 !t136 = sqr# t135 615 !t137 = sqr# t136 616 !t138 = sqr# t137 617 !t139 = sqr# t138 618 !t140 = sqr# t139 619 !t141 = sqr# t140 620 !t142 = sqr# t141 621 !t143 = sqr# t142 622 !t144 = sqr# t143 623 !t145 = sqr# t144 624 !t146 = sqr# t145 625 !t147 = sqr# t146 626 !t148 = sqr# t147 627 !t149 = sqr# t148 628 !t150 = sqr# t149 629 !t151 = sqr# t150 630 !t152 = sqr# t151 631 !t153 = sqr# t152 632 !t154 = sqr# t153 633 !t155 = sqr# t154 634 !t156 = sqr# t155 635 !t157 = sqr# t156 636 !t158 = sqr# t157 637 !t159 = sqr# t158 638 !t160 = sqr# t159 639 !t161 = sqr# t160 640 !t162 = sqr# t161 641 !t163 = sqr# t162 642 !t164 = sqr# t163 643 !t165 = sqr# t164 644 !t166 = sqr# t165 645 !t167 = sqr# t166 646 !t168 = sqr# t167 647 !t169 = sqr# t168 648 !t170 = sqr# t169 649 !t171 = sqr# t170 650 !t172 = sqr# t171 651 !t173 = sqr# t172 652 !t174 = sqr# t173 653 !t175 = sqr# t174 654 !t176 = sqr# t175 655 !t177 = sqr# t176 656 !t178 = sqr# t177 657 !t179 = sqr# t178 658 !t180 = sqr# t179 659 !t181 = sqr# t180 660 !t182 = sqr# t181 661 !t183 = sqr# t182 662 !t184 = sqr# t183 663 !t185 = sqr# t184 664 !t186 = sqr# t185 665 !t187 = sqr# t186 666 !t188 = sqr# t187 667 !t189 = sqr# t188 668 !t190 = sqr# t189 669 !t191 = sqr# t190 670 !t192 = sqr# t191 671 !t193 = sqr# t192 672 !t194 = sqr# t193 673 !t195 = sqr# t194 674 !t196 = sqr# t195 675 !t197 = sqr# t196 676 !t198 = sqr# t197 677 !t199 = mul# t198 t69 678 !t200 = sqr# t199 679 !t201 = sqr# t200 680 !t202 = sqr# t201 681 !t203 = sqr# t202 682 !t204 = sqr# t203 683 !t205 = sqr# t204 684 !t206 = sqr# t205 685 !t207 = sqr# t206 686 !t208 = sqr# t207 687 !t209 = sqr# t208 688 !t210 = sqr# t209 689 !t211 = sqr# t210 690 !t212 = sqr# t211 691 !t213 = sqr# t212 692 !t214 = sqr# t213 693 !t215 = sqr# t214 694 !t216 = mul# t215 t19 695 !t217 = sqr# t216 696 !t218 = sqr# t217 697 !t219 = sqr# t218 698 !t220 = sqr# t219 699 !t221 = sqr# t220 700 !t222 = sqr# t221 701 !t223 = sqr# t222 702 !t224 = sqr# t223 703 !t225 = mul# t224 t10 704 !t226 = sqr# t225 705 !t227 = sqr# t226 706 !t228 = sqr# t227 707 !t229 = sqr# t228 708 !t230 = mul# t229 t5 709 !t231 = sqr# t230 710 !t232 = sqr# t231 711 !t233 = mul# t232 t2 712 !t234 = sqr# t233 713 !t235 = mul# t234 a 714 !t236 = sqr# t19 715 !t237 = sqr# t236 716 !t238 = sqr# t237 717 !t239 = sqr# t238 718 !t240 = mul# t239 t5 719 !t241 = sqr# t240 720 !t242 = sqr# t241 721 !t243 = mul# t242 t2 722 !t244 = sqr# t235 723 !t245 = sqr# t244 724 !t246 = sqr# t245 725 !t247 = sqr# t246 726 !t248 = sqr# t247 727 !t249 = sqr# t248 728 !t250 = sqr# t249 729 !t251 = sqr# t250 730 !t252 = sqr# t251 731 !t253 = sqr# t252 732 !t254 = sqr# t253 733 !t255 = sqr# t254 734 !t256 = sqr# t255 735 !t257 = sqr# t256 736 !t258 = sqr# t257 737 !t259 = sqr# t258 738 !t260 = sqr# t259 739 !t261 = sqr# t260 740 !t262 = sqr# t261 741 !t263 = sqr# t262 742 !t264 = sqr# t263 743 !t265 = sqr# t264 744 !t266 = sqr# t265 745 !t267 = mul# t266 t243 746 !t268 = sqr# t267 747 !t269 = sqr# t268 748 !t270 = sqr# t269 749 !t271 = sqr# t270 750 !t272 = sqr# t271 751 !t273 = mul# t272 a 752 !t274 = sqr# t273 753 !t275 = sqr# t274 754 !t276 = sqr# t275 755 !t277 = mul# t276 t2 756 !t278 = sqr# t277 757 !t279 = sqr# t278 758 !t280 = mul# t279 a 759 !r = t280 760 in r 761 {-# INLINE inv# #-} 762 763 -- | Multiplicative inverse in the Montgomery domain. 764 -- 765 -- Note that 'zero' has no multiplicative inverse; 'inv' returns 766 -- 'zero' when applied to it. 767 -- 768 -- >> inv 2 769 -- 57896044618658097711785492504343953926634992332820282019728792003954417335832 770 -- >> inv 2 * 2 771 -- 1 772 inv :: Montgomery -> Montgomery 773 inv (Montgomery w) = Montgomery (inv# w) 774 775 -- | Square root (Tonelli-Shanks) in the Montgomery domain. 776 -- 777 -- Returns 'Nothing' if the square root doesn't exist. 778 -- 779 -- Note that the square root calculation itself is performed in 780 -- constant time; we branch only when casting to 'Maybe' at the end. 781 -- 782 -- >>> sqrt_vartime 4 783 -- Just 2 784 -- >>> sqrt_vartime 15 785 -- Just 69211104694897500952317515077652022726490027694212560352756646854116994689233 786 -- >>> (*) <$> sqrt_vartime 15 <*> sqrt_vartime 15 787 -- Just 15 788 sqrt_vartime :: Montgomery -> Maybe Montgomery 789 sqrt_vartime (Montgomery n) = case sqrt# n of 790 (# a, c #) 791 | C.decide c -> Just $! Montgomery a 792 | otherwise -> Nothing 793 794 -- generated by etc/generate_sqrt.sh 795 sqrt# 796 :: Limb4 797 -> (# Limb4, C.Choice #) 798 sqrt# a = 799 let !t0 = L4 0x1000003D1## 0## 0## 0## 800 !t1 = sqr# t0 801 !t2 = sqr# t1 802 !t3 = sqr# t2 803 !t4 = mul# a t3 804 !t5 = sqr# t4 805 !t6 = mul# a t5 806 !t7 = sqr# t6 807 !t8 = mul# a t7 808 !t9 = sqr# t8 809 !t10 = mul# a t9 810 !t11 = sqr# t10 811 !t12 = mul# a t11 812 !t13 = sqr# t12 813 !t14 = mul# a t13 814 !t15 = sqr# t14 815 !t16 = mul# a t15 816 !t17 = sqr# t16 817 !t18 = mul# a t17 818 !t19 = sqr# t18 819 !t20 = mul# a t19 820 !t21 = sqr# t20 821 !t22 = mul# a t21 822 !t23 = sqr# t22 823 !t24 = mul# a t23 824 !t25 = sqr# t24 825 !t26 = mul# a t25 826 !t27 = sqr# t26 827 !t28 = mul# a t27 828 !t29 = sqr# t28 829 !t30 = mul# a t29 830 !t31 = sqr# t30 831 !t32 = mul# a t31 832 !t33 = sqr# t32 833 !t34 = mul# a t33 834 !t35 = sqr# t34 835 !t36 = mul# a t35 836 !t37 = sqr# t36 837 !t38 = mul# a t37 838 !t39 = sqr# t38 839 !t40 = mul# a t39 840 !t41 = sqr# t40 841 !t42 = mul# a t41 842 !t43 = sqr# t42 843 !t44 = mul# a t43 844 !t45 = sqr# t44 845 !t46 = mul# a t45 846 !t47 = sqr# t46 847 !t48 = mul# a t47 848 !t49 = sqr# t48 849 !t50 = mul# a t49 850 !t51 = sqr# t50 851 !t52 = mul# a t51 852 !t53 = sqr# t52 853 !t54 = mul# a t53 854 !t55 = sqr# t54 855 !t56 = mul# a t55 856 !t57 = sqr# t56 857 !t58 = mul# a t57 858 !t59 = sqr# t58 859 !t60 = mul# a t59 860 !t61 = sqr# t60 861 !t62 = mul# a t61 862 !t63 = sqr# t62 863 !t64 = mul# a t63 864 !t65 = sqr# t64 865 !t66 = mul# a t65 866 !t67 = sqr# t66 867 !t68 = mul# a t67 868 !t69 = sqr# t68 869 !t70 = mul# a t69 870 !t71 = sqr# t70 871 !t72 = mul# a t71 872 !t73 = sqr# t72 873 !t74 = mul# a t73 874 !t75 = sqr# t74 875 !t76 = mul# a t75 876 !t77 = sqr# t76 877 !t78 = mul# a t77 878 !t79 = sqr# t78 879 !t80 = mul# a t79 880 !t81 = sqr# t80 881 !t82 = mul# a t81 882 !t83 = sqr# t82 883 !t84 = mul# a t83 884 !t85 = sqr# t84 885 !t86 = mul# a t85 886 !t87 = sqr# t86 887 !t88 = mul# a t87 888 !t89 = sqr# t88 889 !t90 = mul# a t89 890 !t91 = sqr# t90 891 !t92 = mul# a t91 892 !t93 = sqr# t92 893 !t94 = mul# a t93 894 !t95 = sqr# t94 895 !t96 = mul# a t95 896 !t97 = sqr# t96 897 !t98 = mul# a t97 898 !t99 = sqr# t98 899 !t100 = mul# a t99 900 !t101 = sqr# t100 901 !t102 = mul# a t101 902 !t103 = sqr# t102 903 !t104 = mul# a t103 904 !t105 = sqr# t104 905 !t106 = mul# a t105 906 !t107 = sqr# t106 907 !t108 = mul# a t107 908 !t109 = sqr# t108 909 !t110 = mul# a t109 910 !t111 = sqr# t110 911 !t112 = mul# a t111 912 !t113 = sqr# t112 913 !t114 = mul# a t113 914 !t115 = sqr# t114 915 !t116 = mul# a t115 916 !t117 = sqr# t116 917 !t118 = mul# a t117 918 !t119 = sqr# t118 919 !t120 = mul# a t119 920 !t121 = sqr# t120 921 !t122 = mul# a t121 922 !t123 = sqr# t122 923 !t124 = mul# a t123 924 !t125 = sqr# t124 925 !t126 = mul# a t125 926 !t127 = sqr# t126 927 !t128 = mul# a t127 928 !t129 = sqr# t128 929 !t130 = mul# a t129 930 !t131 = sqr# t130 931 !t132 = mul# a t131 932 !t133 = sqr# t132 933 !t134 = mul# a t133 934 !t135 = sqr# t134 935 !t136 = mul# a t135 936 !t137 = sqr# t136 937 !t138 = mul# a t137 938 !t139 = sqr# t138 939 !t140 = mul# a t139 940 !t141 = sqr# t140 941 !t142 = mul# a t141 942 !t143 = sqr# t142 943 !t144 = mul# a t143 944 !t145 = sqr# t144 945 !t146 = mul# a t145 946 !t147 = sqr# t146 947 !t148 = mul# a t147 948 !t149 = sqr# t148 949 !t150 = mul# a t149 950 !t151 = sqr# t150 951 !t152 = mul# a t151 952 !t153 = sqr# t152 953 !t154 = mul# a t153 954 !t155 = sqr# t154 955 !t156 = mul# a t155 956 !t157 = sqr# t156 957 !t158 = mul# a t157 958 !t159 = sqr# t158 959 !t160 = mul# a t159 960 !t161 = sqr# t160 961 !t162 = mul# a t161 962 !t163 = sqr# t162 963 !t164 = mul# a t163 964 !t165 = sqr# t164 965 !t166 = mul# a t165 966 !t167 = sqr# t166 967 !t168 = mul# a t167 968 !t169 = sqr# t168 969 !t170 = mul# a t169 970 !t171 = sqr# t170 971 !t172 = mul# a t171 972 !t173 = sqr# t172 973 !t174 = mul# a t173 974 !t175 = sqr# t174 975 !t176 = mul# a t175 976 !t177 = sqr# t176 977 !t178 = mul# a t177 978 !t179 = sqr# t178 979 !t180 = mul# a t179 980 !t181 = sqr# t180 981 !t182 = mul# a t181 982 !t183 = sqr# t182 983 !t184 = mul# a t183 984 !t185 = sqr# t184 985 !t186 = mul# a t185 986 !t187 = sqr# t186 987 !t188 = mul# a t187 988 !t189 = sqr# t188 989 !t190 = mul# a t189 990 !t191 = sqr# t190 991 !t192 = mul# a t191 992 !t193 = sqr# t192 993 !t194 = mul# a t193 994 !t195 = sqr# t194 995 !t196 = mul# a t195 996 !t197 = sqr# t196 997 !t198 = mul# a t197 998 !t199 = sqr# t198 999 !t200 = mul# a t199 1000 !t201 = sqr# t200 1001 !t202 = mul# a t201 1002 !t203 = sqr# t202 1003 !t204 = mul# a t203 1004 !t205 = sqr# t204 1005 !t206 = mul# a t205 1006 !t207 = sqr# t206 1007 !t208 = mul# a t207 1008 !t209 = sqr# t208 1009 !t210 = mul# a t209 1010 !t211 = sqr# t210 1011 !t212 = mul# a t211 1012 !t213 = sqr# t212 1013 !t214 = mul# a t213 1014 !t215 = sqr# t214 1015 !t216 = mul# a t215 1016 !t217 = sqr# t216 1017 !t218 = mul# a t217 1018 !t219 = sqr# t218 1019 !t220 = mul# a t219 1020 !t221 = sqr# t220 1021 !t222 = mul# a t221 1022 !t223 = sqr# t222 1023 !t224 = mul# a t223 1024 !t225 = sqr# t224 1025 !t226 = mul# a t225 1026 !t227 = sqr# t226 1027 !t228 = mul# a t227 1028 !t229 = sqr# t228 1029 !t230 = mul# a t229 1030 !t231 = sqr# t230 1031 !t232 = mul# a t231 1032 !t233 = sqr# t232 1033 !t234 = mul# a t233 1034 !t235 = sqr# t234 1035 !t236 = mul# a t235 1036 !t237 = sqr# t236 1037 !t238 = mul# a t237 1038 !t239 = sqr# t238 1039 !t240 = mul# a t239 1040 !t241 = sqr# t240 1041 !t242 = mul# a t241 1042 !t243 = sqr# t242 1043 !t244 = mul# a t243 1044 !t245 = sqr# t244 1045 !t246 = mul# a t245 1046 !t247 = sqr# t246 1047 !t248 = mul# a t247 1048 !t249 = sqr# t248 1049 !t250 = mul# a t249 1050 !t251 = sqr# t250 1051 !t252 = mul# a t251 1052 !t253 = sqr# t252 1053 !t254 = mul# a t253 1054 !t255 = sqr# t254 1055 !t256 = mul# a t255 1056 !t257 = sqr# t256 1057 !t258 = mul# a t257 1058 !t259 = sqr# t258 1059 !t260 = mul# a t259 1060 !t261 = sqr# t260 1061 !t262 = mul# a t261 1062 !t263 = sqr# t262 1063 !t264 = mul# a t263 1064 !t265 = sqr# t264 1065 !t266 = mul# a t265 1066 !t267 = sqr# t266 1067 !t268 = mul# a t267 1068 !t269 = sqr# t268 1069 !t270 = mul# a t269 1070 !t271 = sqr# t270 1071 !t272 = mul# a t271 1072 !t273 = sqr# t272 1073 !t274 = mul# a t273 1074 !t275 = sqr# t274 1075 !t276 = mul# a t275 1076 !t277 = sqr# t276 1077 !t278 = mul# a t277 1078 !t279 = sqr# t278 1079 !t280 = mul# a t279 1080 !t281 = sqr# t280 1081 !t282 = mul# a t281 1082 !t283 = sqr# t282 1083 !t284 = mul# a t283 1084 !t285 = sqr# t284 1085 !t286 = mul# a t285 1086 !t287 = sqr# t286 1087 !t288 = mul# a t287 1088 !t289 = sqr# t288 1089 !t290 = mul# a t289 1090 !t291 = sqr# t290 1091 !t292 = mul# a t291 1092 !t293 = sqr# t292 1093 !t294 = mul# a t293 1094 !t295 = sqr# t294 1095 !t296 = mul# a t295 1096 !t297 = sqr# t296 1097 !t298 = mul# a t297 1098 !t299 = sqr# t298 1099 !t300 = mul# a t299 1100 !t301 = sqr# t300 1101 !t302 = mul# a t301 1102 !t303 = sqr# t302 1103 !t304 = mul# a t303 1104 !t305 = sqr# t304 1105 !t306 = mul# a t305 1106 !t307 = sqr# t306 1107 !t308 = mul# a t307 1108 !t309 = sqr# t308 1109 !t310 = mul# a t309 1110 !t311 = sqr# t310 1111 !t312 = mul# a t311 1112 !t313 = sqr# t312 1113 !t314 = mul# a t313 1114 !t315 = sqr# t314 1115 !t316 = mul# a t315 1116 !t317 = sqr# t316 1117 !t318 = mul# a t317 1118 !t319 = sqr# t318 1119 !t320 = mul# a t319 1120 !t321 = sqr# t320 1121 !t322 = mul# a t321 1122 !t323 = sqr# t322 1123 !t324 = mul# a t323 1124 !t325 = sqr# t324 1125 !t326 = mul# a t325 1126 !t327 = sqr# t326 1127 !t328 = mul# a t327 1128 !t329 = sqr# t328 1129 !t330 = mul# a t329 1130 !t331 = sqr# t330 1131 !t332 = mul# a t331 1132 !t333 = sqr# t332 1133 !t334 = mul# a t333 1134 !t335 = sqr# t334 1135 !t336 = mul# a t335 1136 !t337 = sqr# t336 1137 !t338 = mul# a t337 1138 !t339 = sqr# t338 1139 !t340 = mul# a t339 1140 !t341 = sqr# t340 1141 !t342 = mul# a t341 1142 !t343 = sqr# t342 1143 !t344 = mul# a t343 1144 !t345 = sqr# t344 1145 !t346 = mul# a t345 1146 !t347 = sqr# t346 1147 !t348 = mul# a t347 1148 !t349 = sqr# t348 1149 !t350 = mul# a t349 1150 !t351 = sqr# t350 1151 !t352 = mul# a t351 1152 !t353 = sqr# t352 1153 !t354 = mul# a t353 1154 !t355 = sqr# t354 1155 !t356 = mul# a t355 1156 !t357 = sqr# t356 1157 !t358 = mul# a t357 1158 !t359 = sqr# t358 1159 !t360 = mul# a t359 1160 !t361 = sqr# t360 1161 !t362 = mul# a t361 1162 !t363 = sqr# t362 1163 !t364 = mul# a t363 1164 !t365 = sqr# t364 1165 !t366 = mul# a t365 1166 !t367 = sqr# t366 1167 !t368 = mul# a t367 1168 !t369 = sqr# t368 1169 !t370 = mul# a t369 1170 !t371 = sqr# t370 1171 !t372 = mul# a t371 1172 !t373 = sqr# t372 1173 !t374 = mul# a t373 1174 !t375 = sqr# t374 1175 !t376 = mul# a t375 1176 !t377 = sqr# t376 1177 !t378 = mul# a t377 1178 !t379 = sqr# t378 1179 !t380 = mul# a t379 1180 !t381 = sqr# t380 1181 !t382 = mul# a t381 1182 !t383 = sqr# t382 1183 !t384 = mul# a t383 1184 !t385 = sqr# t384 1185 !t386 = mul# a t385 1186 !t387 = sqr# t386 1187 !t388 = mul# a t387 1188 !t389 = sqr# t388 1189 !t390 = mul# a t389 1190 !t391 = sqr# t390 1191 !t392 = mul# a t391 1192 !t393 = sqr# t392 1193 !t394 = mul# a t393 1194 !t395 = sqr# t394 1195 !t396 = mul# a t395 1196 !t397 = sqr# t396 1197 !t398 = mul# a t397 1198 !t399 = sqr# t398 1199 !t400 = mul# a t399 1200 !t401 = sqr# t400 1201 !t402 = mul# a t401 1202 !t403 = sqr# t402 1203 !t404 = mul# a t403 1204 !t405 = sqr# t404 1205 !t406 = mul# a t405 1206 !t407 = sqr# t406 1207 !t408 = mul# a t407 1208 !t409 = sqr# t408 1209 !t410 = mul# a t409 1210 !t411 = sqr# t410 1211 !t412 = mul# a t411 1212 !t413 = sqr# t412 1213 !t414 = mul# a t413 1214 !t415 = sqr# t414 1215 !t416 = mul# a t415 1216 !t417 = sqr# t416 1217 !t418 = mul# a t417 1218 !t419 = sqr# t418 1219 !t420 = mul# a t419 1220 !t421 = sqr# t420 1221 !t422 = mul# a t421 1222 !t423 = sqr# t422 1223 !t424 = mul# a t423 1224 !t425 = sqr# t424 1225 !t426 = mul# a t425 1226 !t427 = sqr# t426 1227 !t428 = mul# a t427 1228 !t429 = sqr# t428 1229 !t430 = mul# a t429 1230 !t431 = sqr# t430 1231 !t432 = mul# a t431 1232 !t433 = sqr# t432 1233 !t434 = mul# a t433 1234 !t435 = sqr# t434 1235 !t436 = mul# a t435 1236 !t437 = sqr# t436 1237 !t438 = mul# a t437 1238 !t439 = sqr# t438 1239 !t440 = mul# a t439 1240 !t441 = sqr# t440 1241 !t442 = mul# a t441 1242 !t443 = sqr# t442 1243 !t444 = mul# a t443 1244 !t445 = sqr# t444 1245 !t446 = mul# a t445 1246 !t447 = sqr# t446 1247 !t448 = mul# a t447 1248 !t449 = sqr# t448 1249 !t450 = sqr# t449 1250 !t451 = mul# a t450 1251 !t452 = sqr# t451 1252 !t453 = mul# a t452 1253 !t454 = sqr# t453 1254 !t455 = mul# a t454 1255 !t456 = sqr# t455 1256 !t457 = mul# a t456 1257 !t458 = sqr# t457 1258 !t459 = mul# a t458 1259 !t460 = sqr# t459 1260 !t461 = mul# a t460 1261 !t462 = sqr# t461 1262 !t463 = mul# a t462 1263 !t464 = sqr# t463 1264 !t465 = mul# a t464 1265 !t466 = sqr# t465 1266 !t467 = mul# a t466 1267 !t468 = sqr# t467 1268 !t469 = mul# a t468 1269 !t470 = sqr# t469 1270 !t471 = mul# a t470 1271 !t472 = sqr# t471 1272 !t473 = mul# a t472 1273 !t474 = sqr# t473 1274 !t475 = mul# a t474 1275 !t476 = sqr# t475 1276 !t477 = mul# a t476 1277 !t478 = sqr# t477 1278 !t479 = mul# a t478 1279 !t480 = sqr# t479 1280 !t481 = mul# a t480 1281 !t482 = sqr# t481 1282 !t483 = mul# a t482 1283 !t484 = sqr# t483 1284 !t485 = mul# a t484 1285 !t486 = sqr# t485 1286 !t487 = mul# a t486 1287 !t488 = sqr# t487 1288 !t489 = mul# a t488 1289 !t490 = sqr# t489 1290 !t491 = mul# a t490 1291 !t492 = sqr# t491 1292 !t493 = mul# a t492 1293 !t494 = sqr# t493 1294 !t495 = sqr# t494 1295 !t496 = sqr# t495 1296 !t497 = sqr# t496 1297 !t498 = sqr# t497 1298 !t499 = mul# a t498 1299 !t500 = sqr# t499 1300 !t501 = mul# a t500 1301 !t502 = sqr# t501 1302 !t503 = sqr# t502 1303 !r = t503 1304 in (# r, WW.eq# (sqr# r) a #) 1305 {-# INLINE sqrt# #-} 1306 1307 -- | Exponentiation in the Montgomery domain. 1308 -- 1309 -- >>> exp 2 3 1310 -- 8 1311 -- >>> exp 2 10 1312 -- 1024 1313 exp :: Montgomery -> Wider -> Montgomery 1314 exp (Montgomery b) (Wider e) = Montgomery (exp# b e) 1315 1316 exp# 1317 :: Limb4 1318 -> Limb4 1319 -> Limb4 1320 exp# b e = 1321 let !o = L4 0x1000003D1## 0## 0## 0## 1322 loop !r !m !ex n = case n of 1323 0 -> r 1324 _ -> 1325 let !(# ne, bit #) = WW.shr1_c# ex 1326 !candidate = mul# r m 1327 !nr = select# r candidate bit 1328 !nm = sqr# m 1329 in loop nr nm ne (n - 1) 1330 in loop o b e (256 :: Word) 1331 {-# INLINE exp# #-} 1332 1333 odd# :: Limb4 -> C.Choice 1334 odd# = WW.odd# 1335 {-# INLINE odd# #-} 1336 1337 -- | Check if a 'Montgomery' value is odd. 1338 -- 1339 -- Note that the comparison is performed in constant time, but we 1340 -- branch when converting to 'Bool'. 1341 -- 1342 -- >>> odd 1 1343 -- True 1344 -- >>> odd 2 1345 -- False 1346 -- >>> Data.Word.Wider.odd (retr 3) -- parity is preserved 1347 -- True 1348 odd_vartime :: Montgomery -> Bool 1349 odd_vartime (Montgomery m) = C.decide (odd# m) 1350 1351 -- constant-time selection ---------------------------------------------------- 1352 1353 select# 1354 :: Limb4 -- ^ a 1355 -> Limb4 -- ^ b 1356 -> C.Choice -- ^ c 1357 -> Limb4 -- ^ result 1358 select# = WW.select# 1359 {-# INLINE select# #-} 1360 1361 -- | Return b if c is truthy, otherwise return a. 1362 -- 1363 -- >>> import qualified Data.Choice as C 1364 -- >>> select 0 1 (C.true# ()) 1365 -- 1 1366 select 1367 :: Montgomery -- ^ a 1368 -> Montgomery -- ^ b 1369 -> C.Choice -- ^ c 1370 -> Montgomery -- ^ result 1371 select (Montgomery a) (Montgomery b) c = Montgomery (select# a b c) 1372