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