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