sidef-scripts/Math/square_congruence_lookup_factorization.sf

#!/usr/bin/ruby

# Square congruence lookup-factorization method, for small integers (up to the size of the lookup table).

# OEIS sequences:
#   values of x: https://oeis.org/A306271
#   values of y: https://oeis.org/A306257

# Lookup table up to n=1000
const lookup = %n(0 1 2 2 2 3 4 5 3 3 7 8 4 10 11 4 4 13 6 15 6 5 18 19 5 5 21 6 9 24 8 26 6 7 29 6 6 31 32 8 7 35 10 37 16 7 40 41 7 7 10 10 19 46 12 8 9 14 51 52 8 54 55 8 8 9 14 59 26 16 12 63 9 65 66 10 30 9 19 71 9 9 73 74 10 11 77 22 13 80 14 10 37 23 85 12 10 88 14 10 10 91 26 93 17 11 96 97 12 99 16 29 11 103 28 14 48 11 108 12 11 11 111 31 51 15 16 116 12 32 18 120 14 13 123 12 23 126 35 128 12 37 131 12 12 17 134 14 62 137 20 139 27 13 18 23 16 145 146 43 13 15 18 151 70 13 154 155 13 13 22 14 73 160 47 16 15 46 165 166 14 168 20 50 33 26 49 14 81 15 29 178 14 180 181 14 14 183 20 185 15 53 188 18 20 28 192 16 17 15 22 197 92 58 200 29 15 19 204 59 16 15 61 209 15 15 211 212 25 214 33 16 43 218 22 36 103 65 24 224 16 226 22 18 107 21 68 16 47 70 35 236 16 17 239 16 16 241 70 22 18 19 246 247 17 39 26 73 118 253 24 255 21 17 258 18 32 261 262 20 17 265 80 267 126 17 24 31 17 17 44 80 129 276 28 42 57 19 281 18 20 32 285 85 23 48 26 290 18 86 46 294 19 296 297 18 141 300 89 20 18 91 30 18 18 19 308 92 65 34 26 313 148 23 316 51 19 319 26 97 22 21 28 35 69 19 328 329 41 331 32 20 19 335 101 53 160 19 340 341 19 19 343 22 20 54 103 348 27 25 57 37 43 354 28 20 75 21 30 360 24 110 363 364 20 23 367 26 175 370 28 20 21 112 375 62 20 378 379 20 20 381 115 22 182 21 43 24 23 389 66 118 186 40 32 64 21 119 30 399 22 401 402 28 87 21 122 41 194 23 68 411 21 413 45 22 198 21 127 419 21 21 30 422 55 72 425 130 22 428 30 26 205 131 433 24 25 436 437 22 28 440 32 442 37 23 445 446 22 51 77 137 97 27 139 22 24 40 457 458 22 25 461 22 22 76 36 465 101 143 49 469 62 23 32 24 43 53 146 477 30 145 480 481 23 83 34 26 232 487 32 54 24 23 492 84 64 29 58 151 23 499 38 501 240 23 504 24 23 23 83 43 26 27 155 86 111 157 515 30 24 518 519 158 25 87 34 524 251 44 36 24 29 57 531 26 255 534 40 28 24 25 539 540 71 94 543 24 119 546 34 548 24 169 62 24 24 553 34 170 34 59 172 32 123 27 562 563 28 25 94 175 53 569 38 26 274 176 36 575 25 577 64 47 278 33 179 583 27 25 101 30 26 589 590 28 25 593 184 595 41 25 598 69 25 25 601 26 289 27 36 606 133 188 609 106 83 31 40 49 26 616 191 618 30 29 36 622 27 35 38 26 301 628 193 108 57 50 75 634 26 636 637 28 141 27 55 26 309 200 112 36 26 648 649 26 26 651 200 73 27 202 42 657 28 111 77 203 63 33 38 665 320 27 668 117 35 29 672 208 32 675 40 28 27 31 680 75 92 683 116 53 153 27 38 34 332 214 692 693 27 83 38 215 336 27 44 701 27 27 123 30 97 706 707 28 31 50 59 712 47 29 81 716 37 122 719 64 28 85 40 724 67 226 42 128 30 730 731 28 29 734 229 86 355 31 739 36 28 742 46 232 359 746 61 28 167 29 751 30 28 52 40 28 28 131 236 759 366 235 134 88 29 37 766 34 370 769 40 32 30 67 774 53 106 29 44 241 175 781 42 783 36 245 48 139 29 31 790 30 56 793 248 795 179 29 94 799 32 801 138 251 29 33 250 141 30 29 810 811 29 29 813 253 393 39 65 55 77 254 42 30 113 824 96 32 185 828 46 830 58 31 833 834 30 144 837 34 38 56 44 40 189 71 42 30 118 848 849 265 31 852 42 854 30 37 857 858 49 102 149 30 417 33 269 152 30 31 869 30 30 35 52 32 197 153 274 877 424 73 48 881 31 58 884 38 428 104 44 889 33 278 892 42 32 31 896 74 37 899 46 34 436 283 904 36 31 907 109 284 67 911 286 32 91 31 65 917 130 43 44 289 31 923 80 163 448 31 928 107 31 31 50 76 451 164 44 936 33 35 167 940 36 108 943 32 93 946 295 61 42 86 951 952 53 166 46 34 32 33 48 960 39 302 113 172 137 966 967 32)

func sqcl_factor(n) is cached {

    return []  if n.is_one
    return [n] if (n <= 0)
    return [n] if n.is_prime

    if (n.is_even) {
        var v = n.valuation(2)
        return [v.of(2)..., __FUNC__(n >> v)...]
    }

    if (n > lookup.end) {
        die "#{n} is greater than the size of the lookup table."
    }

    # x^2 = y^2 (mod n), with x >= sqrt(n)
    var x = lookup[n]
    var y = isqrt(x*x % n)

    # Recursively factorize n
    __FUNC__(gcd(x-y, n)) + __FUNC__(gcd(x+y, n))
}

for n in (1..100) {
    var f = sqcl_factor(n).sort
    assert_eq(f, n.factor)
    say ("#{n} -> ", f)
}