/usr/share/doc/libghc-maths-doc/html/src/Math-NumberTheory-Factor.html is in libghc-maths-doc 0.4.5-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 | <?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<head>
<!-- Generated by HsColour, http://code.haskell.org/~malcolm/hscolour/ -->
<title>Math/NumberTheory/Factor.hs</title>
<link type='text/css' rel='stylesheet' href='hscolour.css' />
</head>
<body>
<pre><a name="line-1"></a><span class='hs-comment'>-- Copyright (c) 2006-2011, David Amos. All rights reserved.</span>
<a name="line-2"></a>
<a name="line-3"></a><span class='hs-comment'>-- |A module for finding prime factors.</span>
<a name="line-4"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>Math</span><span class='hs-varop'>.</span><span class='hs-conid'>NumberTheory</span><span class='hs-varop'>.</span><span class='hs-conid'>Factor</span> <span class='hs-layout'>(</span><span class='hs-keyword'>module</span> <span class='hs-conid'>Math</span><span class='hs-varop'>.</span><span class='hs-conid'>NumberTheory</span><span class='hs-varop'>.</span><span class='hs-conid'>Prime</span><span class='hs-layout'>,</span>
<a name="line-5"></a> <span class='hs-varid'>pfactors</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-6"></a>
<a name="line-7"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Math</span><span class='hs-varop'>.</span><span class='hs-conid'>NumberTheory</span><span class='hs-varop'>.</span><span class='hs-conid'>Prime</span>
<a name="line-8"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Either</span> <span class='hs-layout'>(</span><span class='hs-varid'>lefts</span><span class='hs-layout'>)</span>
<a name="line-9"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>List</span> <span class='hs-layout'>(</span><span class='hs-varid'>zip4</span><span class='hs-layout'>)</span>
<a name="line-10"></a>
<a name="line-11"></a><span class='hs-comment'>-- Cohen, A Course in Computational Algebraic Number Theory, p488</span>
<a name="line-12"></a>
<a name="line-13"></a>
<a name="line-14"></a><a name="extendedEuclid"></a><span class='hs-comment'>-- return (u,v,d) s.t ua+vb = d, with d = gcd a b</span>
<a name="line-15"></a><span class='hs-definition'>extendedEuclid</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span>
<a name="line-16"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>b</span> <span class='hs-varop'>==</span> <span class='hs-num'>0</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-num'>1</span><span class='hs-layout'>,</span><span class='hs-num'>0</span><span class='hs-layout'>,</span><span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-17"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-varid'>q</span><span class='hs-layout'>,</span><span class='hs-varid'>r</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>a</span> <span class='hs-varop'>`quotRem`</span> <span class='hs-varid'>b</span> <span class='hs-comment'>-- a == qb + r</span>
<a name="line-18"></a> <span class='hs-layout'>(</span><span class='hs-varid'>s</span><span class='hs-layout'>,</span><span class='hs-varid'>t</span><span class='hs-layout'>,</span><span class='hs-varid'>d</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>extendedEuclid</span> <span class='hs-varid'>b</span> <span class='hs-varid'>r</span> <span class='hs-comment'>-- s*b+t*r == d</span>
<a name="line-19"></a> <span class='hs-keyword'>in</span> <span class='hs-layout'>(</span><span class='hs-varid'>t</span><span class='hs-layout'>,</span><span class='hs-varid'>s</span><span class='hs-comment'>-</span><span class='hs-varid'>q</span><span class='hs-varop'>*</span><span class='hs-varid'>t</span><span class='hs-layout'>,</span><span class='hs-varid'>d</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- s*b+t*(a-q*b) == d</span>
<a name="line-20"></a>
<a name="line-21"></a>
<a name="line-22"></a><span class='hs-comment'>-- ELLIPTIC CURVE ARITHMETIC</span>
<a name="line-23"></a>
<a name="line-24"></a><a name="EllipticCurve"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>EllipticCurve</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>EC</span> <span class='hs-conid'>Integer</span> <span class='hs-conid'>Integer</span> <span class='hs-conid'>Integer</span> <span class='hs-keyword'>deriving</span> <span class='hs-layout'>(</span><span class='hs-conid'>Eq</span><span class='hs-layout'>,</span> <span class='hs-conid'>Show</span><span class='hs-layout'>)</span>
<a name="line-25"></a><span class='hs-comment'>-- EC p a b represents the curve y^2 == x^3+ax+b over Fp</span>
<a name="line-26"></a>
<a name="line-27"></a><a name="EllipticCurvePt"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>EllipticCurvePt</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Inf</span> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>P</span> <span class='hs-conid'>Integer</span> <span class='hs-conid'>Integer</span> <span class='hs-keyword'>deriving</span> <span class='hs-layout'>(</span><span class='hs-conid'>Eq</span><span class='hs-layout'>,</span> <span class='hs-conid'>Show</span><span class='hs-layout'>)</span>
<a name="line-28"></a><span class='hs-comment'>-- P x y</span>
<a name="line-29"></a>
<a name="line-30"></a><a name="isEltEC"></a><span class='hs-definition'>isEltEC</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>Inf</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-31"></a><span class='hs-definition'>isEltEC</span> <span class='hs-layout'>(</span><span class='hs-conid'>EC</span> <span class='hs-varid'>n</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>P</span> <span class='hs-varid'>x</span> <span class='hs-varid'>y</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-varop'>*</span><span class='hs-varid'>y</span> <span class='hs-comment'>-</span> <span class='hs-varid'>x</span><span class='hs-varop'>*</span><span class='hs-varid'>x</span><span class='hs-varop'>*</span><span class='hs-varid'>x</span> <span class='hs-comment'>-</span> <span class='hs-varid'>a</span><span class='hs-varop'>*</span><span class='hs-varid'>x</span> <span class='hs-comment'>-</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span> <span class='hs-varop'>==</span> <span class='hs-num'>0</span>
<a name="line-32"></a>
<a name="line-33"></a>
<a name="line-34"></a><span class='hs-comment'>-- Koblitz p34</span>
<a name="line-35"></a>
<a name="line-36"></a><a name="ecAdd"></a><span class='hs-comment'>-- Addition in an elliptic curve, with bailout if the arithmetic fails (giving a potential factor of n)</span>
<a name="line-37"></a><span class='hs-definition'>ecAdd</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>Inf</span> <span class='hs-varid'>pt</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Right</span> <span class='hs-varid'>pt</span>
<a name="line-38"></a><span class='hs-definition'>ecAdd</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>pt</span> <span class='hs-conid'>Inf</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Right</span> <span class='hs-varid'>pt</span>
<a name="line-39"></a><span class='hs-definition'>ecAdd</span> <span class='hs-layout'>(</span><span class='hs-conid'>EC</span> <span class='hs-varid'>n</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>P</span> <span class='hs-varid'>x1</span> <span class='hs-varid'>y1</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>P</span> <span class='hs-varid'>x2</span> <span class='hs-varid'>y2</span><span class='hs-layout'>)</span>
<a name="line-40"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>x1</span> <span class='hs-varop'>/=</span> <span class='hs-varid'>x2</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-layout'>,</span><span class='hs-varid'>v</span><span class='hs-layout'>,</span><span class='hs-varid'>d</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>extendedEuclid</span> <span class='hs-varid'>n</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>x1</span><span class='hs-comment'>-</span><span class='hs-varid'>x2</span><span class='hs-layout'>)</span> <span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- we're expecting d == 1, v == 1/(x1-x2) (mod n)</span>
<a name="line-41"></a> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>y1</span><span class='hs-comment'>-</span><span class='hs-varid'>y2</span><span class='hs-layout'>)</span> <span class='hs-varop'>*</span> <span class='hs-varid'>v</span> <span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span>
<a name="line-42"></a> <span class='hs-varid'>x3</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>m</span><span class='hs-varop'>*</span><span class='hs-varid'>m</span> <span class='hs-comment'>-</span> <span class='hs-varid'>x1</span> <span class='hs-comment'>-</span> <span class='hs-varid'>x2</span><span class='hs-layout'>)</span> <span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span>
<a name="line-43"></a> <span class='hs-varid'>y3</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-comment'>-</span><span class='hs-varid'>y1</span> <span class='hs-varop'>+</span> <span class='hs-varid'>m</span><span class='hs-varop'>*</span><span class='hs-layout'>(</span><span class='hs-varid'>x1</span> <span class='hs-comment'>-</span> <span class='hs-varid'>x3</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span>
<a name="line-44"></a> <span class='hs-keyword'>in</span> <span class='hs-keyword'>if</span> <span class='hs-varid'>d</span> <span class='hs-varop'>==</span> <span class='hs-num'>1</span> <span class='hs-keyword'>then</span> <span class='hs-conid'>Right</span> <span class='hs-layout'>(</span><span class='hs-conid'>P</span> <span class='hs-varid'>x3</span> <span class='hs-varid'>y3</span><span class='hs-layout'>)</span> <span class='hs-keyword'>else</span> <span class='hs-conid'>Left</span> <span class='hs-varid'>d</span>
<a name="line-45"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>x1</span> <span class='hs-varop'>==</span> <span class='hs-varid'>x2</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>if</span> <span class='hs-layout'>(</span><span class='hs-varid'>y1</span> <span class='hs-varop'>+</span> <span class='hs-varid'>y2</span><span class='hs-layout'>)</span> <span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span> <span class='hs-varop'>==</span> <span class='hs-num'>0</span> <span class='hs-comment'>-- includes the case y1 == y2 == 0</span>
<a name="line-46"></a> <span class='hs-keyword'>then</span> <span class='hs-conid'>Right</span> <span class='hs-conid'>Inf</span>
<a name="line-47"></a> <span class='hs-keyword'>else</span> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-layout'>,</span><span class='hs-varid'>v</span><span class='hs-layout'>,</span><span class='hs-varid'>d</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>extendedEuclid</span> <span class='hs-varid'>n</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-num'>2</span><span class='hs-varop'>*</span><span class='hs-varid'>y1</span><span class='hs-layout'>)</span> <span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span><span class='hs-layout'>)</span> <span class='hs-comment'>-- we're expecting d == 1, v == 1/(2*y1) (mod n)</span>
<a name="line-48"></a> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-num'>3</span><span class='hs-varop'>*</span><span class='hs-varid'>x1</span><span class='hs-varop'>*</span><span class='hs-varid'>x1</span> <span class='hs-varop'>+</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-varop'>*</span> <span class='hs-varid'>v</span> <span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span>
<a name="line-49"></a> <span class='hs-varid'>x3</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>m</span><span class='hs-varop'>*</span><span class='hs-varid'>m</span> <span class='hs-comment'>-</span> <span class='hs-num'>2</span><span class='hs-varop'>*</span><span class='hs-varid'>x1</span><span class='hs-layout'>)</span> <span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span>
<a name="line-50"></a> <span class='hs-varid'>y3</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-comment'>-</span><span class='hs-varid'>y1</span> <span class='hs-varop'>+</span> <span class='hs-varid'>m</span><span class='hs-varop'>*</span><span class='hs-layout'>(</span><span class='hs-varid'>x1</span> <span class='hs-comment'>-</span> <span class='hs-varid'>x3</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span>
<a name="line-51"></a> <span class='hs-keyword'>in</span> <span class='hs-keyword'>if</span> <span class='hs-varid'>d</span> <span class='hs-varop'>==</span> <span class='hs-num'>1</span> <span class='hs-keyword'>then</span> <span class='hs-conid'>Right</span> <span class='hs-layout'>(</span><span class='hs-conid'>P</span> <span class='hs-varid'>x3</span> <span class='hs-varid'>y3</span><span class='hs-layout'>)</span> <span class='hs-keyword'>else</span> <span class='hs-conid'>Left</span> <span class='hs-varid'>d</span>
<a name="line-52"></a><span class='hs-comment'>-- Note that b isn't actually used anywhere</span>
<a name="line-53"></a>
<a name="line-54"></a><span class='hs-comment'>-- Note, only the final `mod` n calls when calculating x3, y3 are necessary</span>
<a name="line-55"></a><span class='hs-comment'>-- and the code is faster if the others are removed</span>
<a name="line-56"></a>
<a name="line-57"></a><a name="ecSmult"></a><span class='hs-comment'>-- Scalar multiplication in an elliptic curve</span>
<a name="line-58"></a><span class='hs-definition'>ecSmult</span> <span class='hs-keyword'>_</span> <span class='hs-num'>0</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Right</span> <span class='hs-conid'>Inf</span>
<a name="line-59"></a><span class='hs-definition'>ecSmult</span> <span class='hs-varid'>ec</span> <span class='hs-varid'>k</span> <span class='hs-varid'>pt</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>k</span> <span class='hs-varop'>></span> <span class='hs-num'>0</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ecSmult'</span> <span class='hs-varid'>k</span> <span class='hs-varid'>pt</span> <span class='hs-conid'>Inf</span>
<a name="line-60"></a> <span class='hs-keyword'>where</span> <span class='hs-comment'>-- ecSmult' k q p = k * q + p</span>
<a name="line-61"></a> <span class='hs-varid'>ecSmult'</span> <span class='hs-num'>0</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Right</span> <span class='hs-varid'>p</span>
<a name="line-62"></a> <span class='hs-varid'>ecSmult'</span> <span class='hs-varid'>i</span> <span class='hs-varid'>q</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>let</span> <span class='hs-varid'>p'</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>if</span> <span class='hs-varid'>odd</span> <span class='hs-varid'>i</span> <span class='hs-keyword'>then</span> <span class='hs-varid'>ecAdd</span> <span class='hs-varid'>ec</span> <span class='hs-varid'>p</span> <span class='hs-varid'>q</span> <span class='hs-keyword'>else</span> <span class='hs-conid'>Right</span> <span class='hs-varid'>p</span>
<a name="line-63"></a> <span class='hs-varid'>q'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ecAdd</span> <span class='hs-varid'>ec</span> <span class='hs-varid'>q</span> <span class='hs-varid'>q</span>
<a name="line-64"></a> <span class='hs-keyword'>in</span> <span class='hs-keyword'>case</span> <span class='hs-layout'>(</span><span class='hs-varid'>p'</span><span class='hs-layout'>,</span><span class='hs-varid'>q'</span><span class='hs-layout'>)</span> <span class='hs-keyword'>of</span>
<a name="line-65"></a> <span class='hs-layout'>(</span><span class='hs-conid'>Right</span> <span class='hs-varid'>p''</span><span class='hs-layout'>,</span> <span class='hs-conid'>Right</span> <span class='hs-varid'>q''</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>ecSmult'</span> <span class='hs-layout'>(</span><span class='hs-varid'>i</span> <span class='hs-varop'>`div`</span> <span class='hs-num'>2</span><span class='hs-layout'>)</span> <span class='hs-varid'>q''</span> <span class='hs-varid'>p''</span>
<a name="line-66"></a> <span class='hs-layout'>(</span><span class='hs-conid'>Left</span> <span class='hs-keyword'>_</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>p'</span>
<a name="line-67"></a> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-layout'>,</span> <span class='hs-conid'>Left</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>q'</span>
<a name="line-68"></a>
<a name="line-69"></a>
<a name="line-70"></a><span class='hs-comment'>-- ELLIPTIC CURVE FACTORISATION</span>
<a name="line-71"></a>
<a name="line-72"></a><span class='hs-comment'>-- We choose an elliptic curve E over Zn, and a point P on the curve</span>
<a name="line-73"></a><span class='hs-comment'>-- We then try to calculate kP, for suitably chosen k</span>
<a name="line-74"></a><span class='hs-comment'>-- What we are hoping is that at some stage we will fail because we can't invert an element in Zn</span>
<a name="line-75"></a><span class='hs-comment'>-- This will lead to finding a non-trivial factor of n</span>
<a name="line-76"></a>
<a name="line-77"></a>
<a name="line-78"></a><a name="discriminantEC"></a><span class='hs-definition'>discriminantEC</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=</span> <span class='hs-num'>4</span> <span class='hs-varop'>*</span> <span class='hs-varid'>a</span> <span class='hs-varop'>*</span> <span class='hs-varid'>a</span> <span class='hs-varop'>*</span> <span class='hs-varid'>a</span> <span class='hs-varop'>+</span> <span class='hs-num'>27</span> <span class='hs-varop'>*</span> <span class='hs-varid'>b</span> <span class='hs-varop'>*</span> <span class='hs-varid'>b</span>
<a name="line-79"></a>
<a name="line-80"></a><a name="ecTrial"></a><span class='hs-comment'>-- perform a sequence of scalar multiplications in the elliptic curve, hoping for a bailout</span>
<a name="line-81"></a><span class='hs-definition'>ecTrial</span> <span class='hs-varid'>ec</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>EC</span> <span class='hs-varid'>n</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-varid'>ms</span> <span class='hs-varid'>pt</span>
<a name="line-82"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>d</span> <span class='hs-varop'>==</span> <span class='hs-num'>1</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ecTrial'</span> <span class='hs-varid'>ms</span> <span class='hs-varid'>pt</span>
<a name="line-83"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Left</span> <span class='hs-varid'>d</span>
<a name="line-84"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>d</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>gcd</span> <span class='hs-varid'>n</span> <span class='hs-layout'>(</span><span class='hs-varid'>discriminantEC</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span>
<a name="line-85"></a> <span class='hs-varid'>ecTrial'</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>pt</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Right</span> <span class='hs-varid'>pt</span>
<a name="line-86"></a> <span class='hs-varid'>ecTrial'</span> <span class='hs-layout'>(</span><span class='hs-varid'>m</span><span class='hs-conop'>:</span><span class='hs-varid'>ms</span><span class='hs-layout'>)</span> <span class='hs-varid'>pt</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>ecSmult</span> <span class='hs-varid'>ec</span> <span class='hs-varid'>m</span> <span class='hs-varid'>pt</span> <span class='hs-keyword'>of</span>
<a name="line-87"></a> <span class='hs-conid'>Right</span> <span class='hs-varid'>pt'</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>ecTrial'</span> <span class='hs-varid'>ms</span> <span class='hs-varid'>pt'</span>
<a name="line-88"></a> <span class='hs-conid'>Left</span> <span class='hs-varid'>d</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Left</span> <span class='hs-varid'>d</span>
<a name="line-89"></a><span class='hs-comment'>-- In effect, we're calculating ecSmult ec (product ms) pt, but an m at a time</span>
<a name="line-90"></a>
<a name="line-91"></a><a name="l"></a><span class='hs-definition'>l</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>exp</span> <span class='hs-layout'>(</span><span class='hs-varid'>sqrt</span> <span class='hs-layout'>(</span><span class='hs-varid'>log</span> <span class='hs-varid'>n</span> <span class='hs-varop'>*</span> <span class='hs-varid'>log</span> <span class='hs-layout'>(</span><span class='hs-varid'>log</span> <span class='hs-varid'>n</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-92"></a><span class='hs-comment'>-- L(n) is some sort of measure of the average smoothness of numbers up to n</span>
<a name="line-93"></a><span class='hs-comment'>-- # [x <= n | x is L(n)^a-smooth] = n L(n)^(-1/2a+o(1)) -- Cohen p 482</span>
<a name="line-94"></a>
<a name="line-95"></a><a name="multipliers"></a><span class='hs-comment'>-- q is the largest prime we're looking for - normally sqrt n</span>
<a name="line-96"></a><span class='hs-comment'>-- the b figure here is from Cohen p488</span>
<a name="line-97"></a><span class='hs-definition'>multipliers</span> <span class='hs-varid'>q</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>p'</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>p</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>takeWhile</span> <span class='hs-layout'>(</span><span class='hs-varop'><=</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-varid'>primes</span><span class='hs-layout'>,</span> <span class='hs-keyword'>let</span> <span class='hs-varid'>p'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>last</span> <span class='hs-layout'>(</span><span class='hs-varid'>takeWhile</span> <span class='hs-layout'>(</span><span class='hs-varop'><=</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>powers</span> <span class='hs-varid'>p</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span>
<a name="line-98"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>round</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>l</span> <span class='hs-varid'>q</span><span class='hs-layout'>)</span> <span class='hs-varop'>**</span> <span class='hs-layout'>(</span><span class='hs-num'>1</span><span class='hs-varop'>/</span><span class='hs-varid'>sqrt</span> <span class='hs-num'>2</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-99"></a> <span class='hs-varid'>powers</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>iterate</span> <span class='hs-layout'>(</span><span class='hs-varop'>*</span><span class='hs-varid'>x</span><span class='hs-layout'>)</span> <span class='hs-varid'>x</span>
<a name="line-100"></a>
<a name="line-101"></a><a name="findFactorECM"></a><span class='hs-definition'>findFactorECM</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>gcd</span> <span class='hs-varid'>n</span> <span class='hs-num'>6</span> <span class='hs-varop'>==</span> <span class='hs-num'>1</span> <span class='hs-keyglyph'>=</span>
<a name="line-102"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>ms</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>multipliers</span> <span class='hs-layout'>(</span><span class='hs-varid'>sqrt</span> <span class='hs-varop'>$</span> <span class='hs-varid'>fromInteger</span> <span class='hs-varid'>n</span><span class='hs-layout'>)</span>
<a name="line-103"></a> <span class='hs-keyword'>in</span> <span class='hs-varid'>head</span> <span class='hs-varop'>$</span> <span class='hs-varid'>filter</span> <span class='hs-layout'>(</span> <span class='hs-layout'>(</span><span class='hs-varop'>/=</span> <span class='hs-num'>0</span><span class='hs-layout'>)</span> <span class='hs-varop'>.</span> <span class='hs-layout'>(</span><span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span><span class='hs-layout'>)</span> <span class='hs-layout'>)</span> <span class='hs-varop'>$</span>
<a name="line-104"></a> <span class='hs-varid'>lefts</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>ecTrial</span> <span class='hs-layout'>(</span><span class='hs-conid'>EC</span> <span class='hs-varid'>n</span> <span class='hs-varid'>a</span> <span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-varid'>ms</span> <span class='hs-layout'>(</span><span class='hs-conid'>P</span> <span class='hs-num'>0</span> <span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'><-</span> <span class='hs-keyglyph'>[</span><span class='hs-num'>1</span><span class='hs-keyglyph'>..</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>]</span>
<a name="line-105"></a> <span class='hs-comment'>-- the filter is because d might be a multiple of n,</span>
<a name="line-106"></a> <span class='hs-comment'>-- for example if the problem was that the discriminant was divisible by n</span>
<a name="line-107"></a>
<a name="line-108"></a>
<a name="line-109"></a><a name="pfactors"></a><span class='hs-comment'>-- |List the prime factors of n (with multiplicity).</span>
<a name="line-110"></a><span class='hs-comment'>-- The algorithm uses trial division to find small factors,</span>
<a name="line-111"></a><span class='hs-comment'>-- followed if necessary by the elliptic curve method to find larger factors.</span>
<a name="line-112"></a><span class='hs-comment'>-- The running time increases with the size of the second largest prime factor of n.</span>
<a name="line-113"></a><span class='hs-comment'>-- It can find 10-digit prime factors in seconds, but can struggle with 20-digit prime factors.</span>
<a name="line-114"></a><span class='hs-definition'>pfactors</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Integer</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Integer</span><span class='hs-keyglyph'>]</span>
<a name="line-115"></a><span class='hs-definition'>pfactors</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>n</span> <span class='hs-varop'>></span> <span class='hs-num'>0</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>pfactors'</span> <span class='hs-varid'>n</span> <span class='hs-varop'>$</span> <span class='hs-varid'>takeWhile</span> <span class='hs-layout'>(</span><span class='hs-varop'><</span> <span class='hs-num'>10000</span><span class='hs-layout'>)</span> <span class='hs-varid'>primes</span>
<a name="line-116"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>n</span> <span class='hs-varop'><</span> <span class='hs-num'>0</span> <span class='hs-keyglyph'>=</span> <span class='hs-comment'>-</span><span class='hs-num'>1</span> <span class='hs-conop'>:</span> <span class='hs-varid'>pfactors'</span> <span class='hs-layout'>(</span><span class='hs-comment'>-</span><span class='hs-varid'>n</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>takeWhile</span> <span class='hs-layout'>(</span><span class='hs-varop'><</span> <span class='hs-num'>10000</span><span class='hs-layout'>)</span> <span class='hs-varid'>primes</span><span class='hs-layout'>)</span>
<a name="line-117"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>pfactors'</span> <span class='hs-varid'>n</span> <span class='hs-layout'>(</span><span class='hs-varid'>d</span><span class='hs-conop'>:</span><span class='hs-varid'>ds</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>n</span> <span class='hs-varop'>==</span> <span class='hs-num'>1</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span>
<a name="line-118"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>n</span> <span class='hs-varop'><</span> <span class='hs-varid'>d</span><span class='hs-varop'>*</span><span class='hs-varid'>d</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>n</span><span class='hs-keyglyph'>]</span>
<a name="line-119"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>r</span> <span class='hs-varop'>==</span> <span class='hs-num'>0</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>d</span> <span class='hs-conop'>:</span> <span class='hs-varid'>pfactors'</span> <span class='hs-varid'>q</span> <span class='hs-layout'>(</span><span class='hs-varid'>d</span><span class='hs-conop'>:</span><span class='hs-varid'>ds</span><span class='hs-layout'>)</span>
<a name="line-120"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>pfactors'</span> <span class='hs-varid'>n</span> <span class='hs-varid'>ds</span>
<a name="line-121"></a> <span class='hs-keyword'>where</span> <span class='hs-layout'>(</span><span class='hs-varid'>q</span><span class='hs-layout'>,</span><span class='hs-varid'>r</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>quotRem</span> <span class='hs-varid'>n</span> <span class='hs-varid'>d</span>
<a name="line-122"></a> <span class='hs-varid'>pfactors'</span> <span class='hs-varid'>n</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>pfactors''</span> <span class='hs-varid'>n</span>
<a name="line-123"></a> <span class='hs-varid'>pfactors''</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>if</span> <span class='hs-varid'>isMillerRabinPrime</span> <span class='hs-varid'>n</span> <span class='hs-keyword'>then</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>n</span><span class='hs-keyglyph'>]</span>
<a name="line-124"></a> <span class='hs-keyword'>else</span> <span class='hs-keyword'>let</span> <span class='hs-varid'>d</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>findFactorParallelECM</span> <span class='hs-varid'>n</span> <span class='hs-comment'>-- findFactorECM n</span>
<a name="line-125"></a> <span class='hs-keyword'>in</span> <span class='hs-varid'>merge</span> <span class='hs-layout'>(</span><span class='hs-varid'>pfactors''</span> <span class='hs-varid'>d</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>pfactors''</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span> <span class='hs-varop'>`div`</span> <span class='hs-varid'>d</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-126"></a>
<a name="line-127"></a><a name="merge"></a><span class='hs-definition'>merge</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-128"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>compare</span> <span class='hs-varid'>x</span> <span class='hs-varid'>y</span> <span class='hs-keyword'>of</span>
<a name="line-129"></a> <span class='hs-conid'>LT</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>x</span> <span class='hs-conop'>:</span> <span class='hs-varid'>merge</span> <span class='hs-varid'>xs</span> <span class='hs-layout'>(</span><span class='hs-varid'>y</span><span class='hs-conop'>:</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span>
<a name="line-130"></a> <span class='hs-conid'>EQ</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>x</span> <span class='hs-conop'>:</span> <span class='hs-varid'>y</span> <span class='hs-conop'>:</span> <span class='hs-varid'>merge</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>ys</span>
<a name="line-131"></a> <span class='hs-conid'>GT</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>y</span> <span class='hs-conop'>:</span> <span class='hs-varid'>merge</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-varid'>ys</span>
<a name="line-132"></a><span class='hs-definition'>merge</span> <span class='hs-varid'>xs</span> <span class='hs-varid'>ys</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>xs</span> <span class='hs-varop'>++</span> <span class='hs-varid'>ys</span>
<a name="line-133"></a>
<a name="line-134"></a>
<a name="line-135"></a><a name="parallelInverse"></a><span class='hs-comment'>-- Cohen p489</span>
<a name="line-136"></a><span class='hs-comment'>-- find inverse of as mod n in parallel, or a non-trivial factor of n</span>
<a name="line-137"></a><span class='hs-definition'>parallelInverse</span> <span class='hs-varid'>n</span> <span class='hs-keyword'>as</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>if</span> <span class='hs-varid'>d</span> <span class='hs-varop'>==</span> <span class='hs-num'>1</span> <span class='hs-keyword'>then</span> <span class='hs-conid'>Right</span> <span class='hs-varid'>bs</span> <span class='hs-keyword'>else</span> <span class='hs-conid'>Left</span> <span class='hs-varop'>$</span> <span class='hs-varid'>head</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>d'</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'><-</span> <span class='hs-keyword'>as</span><span class='hs-layout'>,</span> <span class='hs-keyword'>let</span> <span class='hs-varid'>d'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>gcd</span> <span class='hs-varid'>a</span> <span class='hs-varid'>n</span><span class='hs-layout'>,</span> <span class='hs-varid'>d'</span> <span class='hs-varop'>/=</span> <span class='hs-num'>1</span><span class='hs-keyglyph'>]</span>
<a name="line-138"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>c</span><span class='hs-conop'>:</span><span class='hs-varid'>cs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>reverse</span> <span class='hs-varop'>$</span> <span class='hs-varid'>scanl</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>x</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>x</span><span class='hs-varop'>*</span><span class='hs-varid'>y</span> <span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span><span class='hs-layout'>)</span> <span class='hs-num'>1</span> <span class='hs-keyword'>as</span>
<a name="line-139"></a> <span class='hs-varid'>ds</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>scanl</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>x</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>x</span><span class='hs-varop'>*</span><span class='hs-varid'>y</span> <span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span><span class='hs-layout'>)</span> <span class='hs-num'>1</span> <span class='hs-layout'>(</span><span class='hs-varid'>reverse</span> <span class='hs-keyword'>as</span><span class='hs-layout'>)</span>
<a name="line-140"></a> <span class='hs-layout'>(</span><span class='hs-varid'>u</span><span class='hs-layout'>,</span><span class='hs-keyword'>_</span><span class='hs-layout'>,</span><span class='hs-varid'>d</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>extendedEuclid</span> <span class='hs-varid'>c</span> <span class='hs-varid'>n</span>
<a name="line-141"></a> <span class='hs-varid'>bs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>reverse</span> <span class='hs-keyglyph'>[</span> <span class='hs-varid'>u</span><span class='hs-varop'>*</span><span class='hs-varid'>nota</span> <span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>nota</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>zipWith</span> <span class='hs-layout'>(</span><span class='hs-varop'>*</span><span class='hs-layout'>)</span> <span class='hs-varid'>cs</span> <span class='hs-varid'>ds</span><span class='hs-keyglyph'>]</span>
<a name="line-142"></a><span class='hs-comment'>-- let m = length as</span>
<a name="line-143"></a><span class='hs-comment'>-- then the above code requires O(m) mod calls - in fact 3m-3 calls (?)</span>
<a name="line-144"></a>
<a name="line-145"></a><a name="parallelEcAdd"></a><span class='hs-definition'>parallelEcAdd</span> <span class='hs-varid'>n</span> <span class='hs-varid'>ecs</span> <span class='hs-varid'>ps1</span> <span class='hs-varid'>ps2</span> <span class='hs-keyglyph'>=</span>
<a name="line-146"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>parallelInverse</span> <span class='hs-varid'>n</span> <span class='hs-layout'>(</span><span class='hs-varid'>zipWith</span> <span class='hs-varid'>f</span> <span class='hs-varid'>ps1</span> <span class='hs-varid'>ps2</span><span class='hs-layout'>)</span> <span class='hs-keyword'>of</span>
<a name="line-147"></a> <span class='hs-conid'>Right</span> <span class='hs-varid'>invs</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Right</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>g</span> <span class='hs-varid'>ec</span> <span class='hs-varid'>p1</span> <span class='hs-varid'>p2</span> <span class='hs-varid'>inv</span> <span class='hs-keyglyph'>|</span> <span class='hs-layout'>(</span><span class='hs-varid'>ec</span><span class='hs-layout'>,</span><span class='hs-varid'>p1</span><span class='hs-layout'>,</span><span class='hs-varid'>p2</span><span class='hs-layout'>,</span><span class='hs-varid'>inv</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>zip4</span> <span class='hs-varid'>ecs</span> <span class='hs-varid'>ps1</span> <span class='hs-varid'>ps2</span> <span class='hs-varid'>invs</span><span class='hs-keyglyph'>]</span>
<a name="line-148"></a> <span class='hs-conid'>Left</span> <span class='hs-varid'>d</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Left</span> <span class='hs-varid'>d</span>
<a name="line-149"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>f</span> <span class='hs-conid'>Inf</span> <span class='hs-varid'>pt</span> <span class='hs-keyglyph'>=</span> <span class='hs-num'>1</span>
<a name="line-150"></a> <span class='hs-varid'>f</span> <span class='hs-varid'>pt</span> <span class='hs-conid'>Inf</span> <span class='hs-keyglyph'>=</span> <span class='hs-num'>1</span>
<a name="line-151"></a> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>P</span> <span class='hs-varid'>x1</span> <span class='hs-varid'>y1</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>P</span> <span class='hs-varid'>x2</span> <span class='hs-varid'>y2</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>x1</span> <span class='hs-varop'>/=</span> <span class='hs-varid'>x2</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>x1</span><span class='hs-comment'>-</span><span class='hs-varid'>x2</span> <span class='hs-comment'>-- slightly faster not to `mod` n here</span>
<a name="line-152"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>x1</span> <span class='hs-varop'>==</span> <span class='hs-varid'>x2</span> <span class='hs-keyglyph'>=</span> <span class='hs-num'>2</span><span class='hs-varop'>*</span><span class='hs-varid'>y1</span> <span class='hs-comment'>-- slightly faster not to `mod` n here</span>
<a name="line-153"></a> <span class='hs-comment'>-- inverses = parallelInverse n $ zipWith f ps1 ps2</span>
<a name="line-154"></a> <span class='hs-varid'>g</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>Inf</span> <span class='hs-varid'>pt</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>pt</span>
<a name="line-155"></a> <span class='hs-varid'>g</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>pt</span> <span class='hs-conid'>Inf</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>pt</span>
<a name="line-156"></a> <span class='hs-varid'>g</span> <span class='hs-layout'>(</span><span class='hs-conid'>EC</span> <span class='hs-varid'>n</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>P</span> <span class='hs-varid'>x1</span> <span class='hs-varid'>y1</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>P</span> <span class='hs-varid'>x2</span> <span class='hs-varid'>y2</span><span class='hs-layout'>)</span> <span class='hs-varid'>inv</span>
<a name="line-157"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>x1</span> <span class='hs-varop'>/=</span> <span class='hs-varid'>x2</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>let</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>y1</span><span class='hs-comment'>-</span><span class='hs-varid'>y2</span><span class='hs-layout'>)</span> <span class='hs-varop'>*</span> <span class='hs-varid'>inv</span> <span class='hs-comment'>-- slightly faster not to `mod` n here</span>
<a name="line-158"></a> <span class='hs-varid'>x3</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>m</span><span class='hs-varop'>*</span><span class='hs-varid'>m</span> <span class='hs-comment'>-</span> <span class='hs-varid'>x1</span> <span class='hs-comment'>-</span> <span class='hs-varid'>x2</span><span class='hs-layout'>)</span> <span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span>
<a name="line-159"></a> <span class='hs-varid'>y3</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-comment'>-</span><span class='hs-varid'>y1</span> <span class='hs-varop'>+</span> <span class='hs-varid'>m</span><span class='hs-varop'>*</span><span class='hs-layout'>(</span><span class='hs-varid'>x1</span> <span class='hs-comment'>-</span> <span class='hs-varid'>x3</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span>
<a name="line-160"></a> <span class='hs-keyword'>in</span> <span class='hs-conid'>P</span> <span class='hs-varid'>x3</span> <span class='hs-varid'>y3</span>
<a name="line-161"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>x1</span> <span class='hs-varop'>==</span> <span class='hs-varid'>x2</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>if</span> <span class='hs-layout'>(</span><span class='hs-varid'>y1</span> <span class='hs-varop'>+</span> <span class='hs-varid'>y2</span><span class='hs-layout'>)</span> <span class='hs-varop'>`elem`</span> <span class='hs-keyglyph'>[</span><span class='hs-num'>0</span><span class='hs-layout'>,</span><span class='hs-varid'>n</span><span class='hs-keyglyph'>]</span> <span class='hs-comment'>-- `mod` n == 0 -- includes the case y1 == y2 == 0</span>
<a name="line-162"></a> <span class='hs-keyword'>then</span> <span class='hs-conid'>Inf</span>
<a name="line-163"></a> <span class='hs-keyword'>else</span> <span class='hs-keyword'>let</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-num'>3</span><span class='hs-varop'>*</span><span class='hs-varid'>x1</span><span class='hs-varop'>*</span><span class='hs-varid'>x1</span> <span class='hs-varop'>+</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-varop'>*</span> <span class='hs-varid'>inv</span> <span class='hs-comment'>-- slightly faster not to `mod` n here</span>
<a name="line-164"></a> <span class='hs-varid'>x3</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>m</span><span class='hs-varop'>*</span><span class='hs-varid'>m</span> <span class='hs-comment'>-</span> <span class='hs-num'>2</span><span class='hs-varop'>*</span><span class='hs-varid'>x1</span><span class='hs-layout'>)</span> <span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span>
<a name="line-165"></a> <span class='hs-varid'>y3</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-comment'>-</span><span class='hs-varid'>y1</span> <span class='hs-varop'>+</span> <span class='hs-varid'>m</span><span class='hs-varop'>*</span><span class='hs-layout'>(</span><span class='hs-varid'>x1</span> <span class='hs-comment'>-</span> <span class='hs-varid'>x3</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span>
<a name="line-166"></a> <span class='hs-keyword'>in</span> <span class='hs-conid'>P</span> <span class='hs-varid'>x3</span> <span class='hs-varid'>y3</span>
<a name="line-167"></a>
<a name="line-168"></a><a name="parallelEcSmult"></a><span class='hs-definition'>parallelEcSmult</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-num'>0</span> <span class='hs-varid'>pts</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Right</span> <span class='hs-varop'>$</span> <span class='hs-varid'>map</span> <span class='hs-layout'>(</span><span class='hs-varid'>const</span> <span class='hs-conid'>Inf</span><span class='hs-layout'>)</span> <span class='hs-varid'>pts</span>
<a name="line-169"></a><span class='hs-definition'>parallelEcSmult</span> <span class='hs-varid'>n</span> <span class='hs-varid'>ecs</span> <span class='hs-varid'>k</span> <span class='hs-varid'>pts</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>k</span> <span class='hs-varop'>></span> <span class='hs-num'>0</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ecSmult'</span> <span class='hs-varid'>k</span> <span class='hs-varid'>pts</span> <span class='hs-layout'>(</span><span class='hs-varid'>map</span> <span class='hs-layout'>(</span><span class='hs-varid'>const</span> <span class='hs-conid'>Inf</span><span class='hs-layout'>)</span> <span class='hs-varid'>pts</span><span class='hs-layout'>)</span>
<a name="line-170"></a> <span class='hs-keyword'>where</span> <span class='hs-comment'>-- ecSmult' k qs ps = k * qs + ps</span>
<a name="line-171"></a> <span class='hs-varid'>ecSmult'</span> <span class='hs-num'>0</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>ps</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Right</span> <span class='hs-varid'>ps</span>
<a name="line-172"></a> <span class='hs-varid'>ecSmult'</span> <span class='hs-varid'>k</span> <span class='hs-varid'>qs</span> <span class='hs-varid'>ps</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>let</span> <span class='hs-varid'>ps'</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>if</span> <span class='hs-varid'>odd</span> <span class='hs-varid'>k</span> <span class='hs-keyword'>then</span> <span class='hs-varid'>parallelEcAdd</span> <span class='hs-varid'>n</span> <span class='hs-varid'>ecs</span> <span class='hs-varid'>ps</span> <span class='hs-varid'>qs</span> <span class='hs-keyword'>else</span> <span class='hs-conid'>Right</span> <span class='hs-varid'>ps</span>
<a name="line-173"></a> <span class='hs-varid'>qs'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>parallelEcAdd</span> <span class='hs-varid'>n</span> <span class='hs-varid'>ecs</span> <span class='hs-varid'>qs</span> <span class='hs-varid'>qs</span>
<a name="line-174"></a> <span class='hs-keyword'>in</span> <span class='hs-keyword'>case</span> <span class='hs-layout'>(</span><span class='hs-varid'>ps'</span><span class='hs-layout'>,</span><span class='hs-varid'>qs'</span><span class='hs-layout'>)</span> <span class='hs-keyword'>of</span>
<a name="line-175"></a> <span class='hs-layout'>(</span><span class='hs-conid'>Right</span> <span class='hs-varid'>ps''</span><span class='hs-layout'>,</span> <span class='hs-conid'>Right</span> <span class='hs-varid'>qs''</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>ecSmult'</span> <span class='hs-layout'>(</span><span class='hs-varid'>k</span> <span class='hs-varop'>`div`</span> <span class='hs-num'>2</span><span class='hs-layout'>)</span> <span class='hs-varid'>qs''</span> <span class='hs-varid'>ps''</span>
<a name="line-176"></a> <span class='hs-layout'>(</span><span class='hs-conid'>Left</span> <span class='hs-keyword'>_</span><span class='hs-layout'>,</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>ps'</span>
<a name="line-177"></a> <span class='hs-layout'>(</span><span class='hs-keyword'>_</span><span class='hs-layout'>,</span> <span class='hs-conid'>Left</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>qs'</span>
<a name="line-178"></a>
<a name="line-179"></a><a name="parallelEcTrial"></a><span class='hs-definition'>parallelEcTrial</span> <span class='hs-varid'>n</span> <span class='hs-varid'>ecs</span> <span class='hs-varid'>ms</span> <span class='hs-varid'>pts</span>
<a name="line-180"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>all</span> <span class='hs-layout'>(</span><span class='hs-varop'>==</span><span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-varid'>ds</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>ecTrial'</span> <span class='hs-varid'>ms</span> <span class='hs-varid'>pts</span>
<a name="line-181"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Left</span> <span class='hs-varop'>$</span> <span class='hs-varid'>head</span> <span class='hs-varop'>$</span> <span class='hs-varid'>filter</span> <span class='hs-layout'>(</span><span class='hs-varop'>/=</span><span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-varid'>ds</span>
<a name="line-182"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>ds</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>gcd</span> <span class='hs-varid'>n</span> <span class='hs-layout'>(</span><span class='hs-varid'>discriminantEC</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>EC</span> <span class='hs-varid'>n</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>ecs</span><span class='hs-keyglyph'>]</span>
<a name="line-183"></a> <span class='hs-varid'>ecTrial'</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>pts</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Right</span> <span class='hs-varid'>pts</span>
<a name="line-184"></a> <span class='hs-varid'>ecTrial'</span> <span class='hs-layout'>(</span><span class='hs-varid'>m</span><span class='hs-conop'>:</span><span class='hs-varid'>ms</span><span class='hs-layout'>)</span> <span class='hs-varid'>pts</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>parallelEcSmult</span> <span class='hs-varid'>n</span> <span class='hs-varid'>ecs</span> <span class='hs-varid'>m</span> <span class='hs-varid'>pts</span> <span class='hs-keyword'>of</span>
<a name="line-185"></a> <span class='hs-conid'>Right</span> <span class='hs-varid'>pts'</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>ecTrial'</span> <span class='hs-varid'>ms</span> <span class='hs-varid'>pts'</span>
<a name="line-186"></a> <span class='hs-conid'>Left</span> <span class='hs-varid'>d</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Left</span> <span class='hs-varid'>d</span>
<a name="line-187"></a>
<a name="line-188"></a><a name="findFactorParallelECM"></a><span class='hs-definition'>findFactorParallelECM</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>gcd</span> <span class='hs-varid'>n</span> <span class='hs-num'>6</span> <span class='hs-varop'>==</span> <span class='hs-num'>1</span> <span class='hs-keyglyph'>=</span>
<a name="line-189"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>ms</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>multipliers</span> <span class='hs-layout'>(</span><span class='hs-varid'>sqrt</span> <span class='hs-varop'>$</span> <span class='hs-varid'>fromInteger</span> <span class='hs-varid'>n</span><span class='hs-layout'>)</span>
<a name="line-190"></a> <span class='hs-keyword'>in</span> <span class='hs-varid'>head</span> <span class='hs-varop'>$</span> <span class='hs-varid'>filter</span> <span class='hs-layout'>(</span> <span class='hs-layout'>(</span><span class='hs-varop'>/=</span> <span class='hs-num'>0</span><span class='hs-layout'>)</span> <span class='hs-varop'>.</span> <span class='hs-layout'>(</span><span class='hs-varop'>`mod`</span> <span class='hs-varid'>n</span><span class='hs-layout'>)</span> <span class='hs-layout'>)</span> <span class='hs-varop'>$</span>
<a name="line-191"></a> <span class='hs-varid'>lefts</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>parallelEcTrial</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>EC</span> <span class='hs-varid'>n</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span><span class='hs-varop'>+</span><span class='hs-varid'>i</span><span class='hs-layout'>)</span> <span class='hs-num'>1</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>i</span> <span class='hs-keyglyph'><-</span> <span class='hs-keyglyph'>[</span><span class='hs-num'>1</span><span class='hs-keyglyph'>..</span><span class='hs-num'>100</span><span class='hs-keyglyph'>]</span><span class='hs-keyglyph'>]</span> <span class='hs-varid'>ms</span> <span class='hs-layout'>(</span><span class='hs-varid'>replicate</span> <span class='hs-num'>100</span> <span class='hs-layout'>(</span><span class='hs-conid'>P</span> <span class='hs-num'>0</span> <span class='hs-num'>1</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'><-</span> <span class='hs-keyglyph'>[</span><span class='hs-num'>0</span><span class='hs-layout'>,</span><span class='hs-num'>100</span><span class='hs-keyglyph'>..</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>]</span>
<a name="line-192"></a><span class='hs-comment'>-- 100 at a time is chosen heuristically.</span>
<a name="line-193"></a>
</pre></body>
</html>
|