sidef-scripts/Math/pocklington-pratt_primality_proving.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 05 January 2020
# https://github.com/trizen

# Prove the primality of a number, using the Pocklington primality test recursively.

# See also:
#   https://en.wikipedia.org/wiki/Pocklington_primality_test
#   https://en.wikipedia.org/wiki/Primality_certificate
#   https://mathworld.wolfram.com/PrattCertificate.html

func pocklington_pratt_primality_test(n, lim=2**64) is cached {

    if ((n <= lim) || (n <= 2)) {
        return n.is_prime
    }

    n.is_prob_prime || return false

    var d = n-1
    var f = d.trial_factor(1e6)
    var B = f.pop

    if (__FUNC__(B)) {
        f << B
        B = 1
    }

    func prove_primality() {
        f.uniq.all {|p|
            1..Inf -> any {
                var a = irand(2, d)
                n.is_strong_pseudoprime(a) || return false
                if (is_coprime(powmod(a, d/p, n) - 1, n)) {
                    say [a, p]
                    true
                }
                else {
                    false
                }
            }
        }
    }

    loop {
        var A = f.prod

        if (A>B && is_coprime(A, B)) {
            say "\n:: Proving primality of: #{n}"
            return prove_primality()
        }

        var e = B.ecm_factor.grep(__FUNC__)
        f += e
        B /= e.prod
    }
}

say pocklington_pratt_primality_test(115792089237316195423570985008687907853269984665640564039457584007913129603823)

__END__
:: Proving primality of: 1202684276868524221513588244947
[1144035226262155255816851107163, 2]
[276453507044821683122757236393, 3]
[533055736413590411441630243028, 192697]
[772623052663915357147976998514, 5829139]
[1198620610208329295067901446571, 59483944987587859]

:: Proving primality of: 3201964079152361724098258636758155557
[2313084224942214561921893626258798444, 2]
[1693916761993490383400547587005461017, 13]
[2263618819408762859220408720925669846, 51199]
[2103416709313180536403627832549882073, 1202684276868524221513588244947]

:: Proving primality of: 2848630210554880446022254608450222949126931851754251657020267
[2336186877965705181223610367257376615859197600261422793430493, 2]
[1241720120219776264682254065631971571331550672156703004094326, 7]
[18307568000383431510493991654897777639917722928696705126173, 71]
[1489831621568319391708979957772210592834553663557254011479744, 397]
[1824425577446593185257046318868196863269017909587463235878344, 22483]
[807398507928647255183839098063474859547898067727177143487761, 100274029791527]
[2134990251409720802017140664124255058534215247184945285413251, 3201964079152361724098258636758155557]

:: Proving primality of: 57896044618658097711785492504343953926634992332820282019728792003956564801911
[35223411003114110927962766028347501904174744824558491409391205156094574988512, 2]
[43706303540610111065034740159703946431199181276874121569813825440977188904287, 5]
[4140586583236580449118971852137382265992219704057140377213024358453134888045, 19]
[28382269783315586931299470473225360074904358956236329373293103791422688635474, 106969315701167]
[6481591555917417607160527003167957443419742853878784194511937548702782864566, 2848630210554880446022254608450222949126931851754251657020267]

:: Proving primality of: 115792089237316195423570985008687907853269984665640564039457584007913129603823
[87251640571289373727381043576536706375458762721304644901612327104869487452319, 2]
[59269750266327054665432205978695482013726314612623402701790265449453177692176, 57896044618658097711785492504343953926634992332820282019728792003956564801911]
true