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