frobenius_pseudoprimes_generation.pl

#!/usr/bin/perl

# Author: Daniel "Trizen" Șuteu
# Date: 07 October 2018
# Edit: 19 August 2020
# https://github.com/trizen

# A new algorithm for generating Frobenius pseudoprimes to Fibonacci polynomial x^2 - x - 1.

# See also:
#   https://oeis.org/A217120 -- Lucas pseudoprimes
#   https://oeis.org/A217255 -- Strong Lucas pseudoprimes
#   https://oeis.org/A177745 -- Semiprimes n such that n divides Fibonacci(n+1).
#   https://oeis.org/A212423 -- Frobenius pseudoprimes == 2,3 (mod 5) with respect to Fibonacci polynomial x^2 - x - 1.

# See also:
#   https://trizenx.blogspot.com/2020/08/pseudoprimes-construction-methods-and.html

use 5.020;
use warnings;
use experimental qw(signatures);

use ntheory qw(:all);
use Math::AnyNum qw(prod);

sub frobenius_pseudoprimes ($limit, $callback, $P = 1, $Q = -1) {

    my %table;
    my $D = $P*$P - 4*$Q;

    forprimes {
        my $p = $_;
        foreach my $d (divisors($p - kronecker($D, $p))) {
            if ((lucas_sequence($p, $P, $Q, $d))[0] == 0) {
                push @{$table{$d}}, $p;
                last;
            }
        }
    } 3, $limit;

    foreach my $arr (values %table) {

        my $l = $#{$arr} + 1;

        foreach my $k (2 .. $l) {
            forcomb {
                my $n = prod(@{$arr}[@_]);
                $callback->($n, @{$arr}[@_]);
            } $l, $k;
        }
    }
}

my @pseudoprimes;

frobenius_pseudoprimes(
    100_000,
    sub ($n, @f) {

        is_frobenius_pseudoprime($n, 1, -1) or die "error: $n";

        push @pseudoprimes, $n;

        if (kronecker(5, $n) == -1 and powmod(2, $n-1, $n) == 1) {
            die "Found a BPSW counter-example: $n = prod(@f)";
        }
    }
);

@pseudoprimes = sort { $a <=> $b } @pseudoprimes;

say join(', ', @pseudoprimes);

__END__
4181, 5777, 10877, 13201, 15251, 64079, 64681, 67861, 75077, 97921, 100127, 113573, 118441, 161027, 162133, 219781, 231703, 254321, 272611, 330929, 430127, 556421, 638189, 722261, 741751, 851927, 999941, 1033997, 1106561, 1149851, 1256293, 1346269, 1392169, 1690501, 2159389, 2187841, 2221811, 2263127, 2362081, 2435423, 2465101, 2476549, 2559929, 2586229, 2662277, 3175883, 3188011, 3218801, 3399527, 3568661, 3636121, 3663871, 4226777, 4250681, 4403027, 4868641, 4870847, 4974481, 5208377, 5328181, 5800001, 5942627, 6003923, 6192721, 6359021, 6374111, 6884131, 7067171, 7369601, 7879681, 7947701, 7961801, 8518127, 8655511, 8834641, 9401893, 9476741, 9713027, 9922337, 10054043, 10403641, 10604431, 10837601, 11487961, 11637583, 12178241, 12962291, 13012651, 13277423, 13404751, 13455077, 14015843, 14787181, 14892541, 14985833, 15287009, 15754007, 16233361, 16485493, 16685003, 18552361, 18557951, 19168477, 20551301, 21692189, 21850951, 21988961, 22361327, 22556801, 22591301, 23292361, 23307377, 24157817, 24236461, 24493061, 25532501, 25707841, 27236311, 29604893, 29971811, 30299333, 31150351, 31155001, 31181581, 31530241, 31673333, 32092259, 32377591, 32702723, 32815361, 33664651, 33796531, 34134407, 34379101, 35365111, 35452891, 36574849, 39247393, 40433551, 40465501, 40629601, 40675981, 41177993, 41808581, 42149971, 42389027, 42525773, 43259221, 43701901, 44111629, 44370481, 46114921, 47219201, 47297543, 49219673, 51132251, 51931333, 52448371, 53835031, 54675571, 55530161, 55681841, 55726849, 57028949, 57280081, 57464207, 57903361, 59268827, 60881921, 61218901, 61770041, 64610027, 66124001, 66347849, 66796529, 67237883, 70894277, 73295777, 73693369, 73780877, 74580767, 75239513, 75245777, 77337941, 77642881, 77862391, 78430801, 83241013, 83963177, 83967361, 84292249, 84792811, 85015493, 85090339, 85518229, 85903277, 87160061, 87471017, 89190301, 89784581, 89816411, 93591569, 95452781, 97894501, 98385377, 100224001, 101159119, 101873441, 104943827, 106314931, 109231229, 110734667, 116853827, 117987841, 119710951, 120485381, 121152961, 121226531, 122505571, 123247001, 124477513, 127835341, 131369801, 132162581, 132245291, 136579127, 138652879, 139904627, 140707921, 142593827, 143548501, 145206361, 146206901, 148436209, 148472347, 152396641, 154285721, 157132127, 157793659, 158197577, 159160751, 161216021, 161438671, 163578827, 165580141, 166850777, 167364161, 168018353, 168600329, 170173741, 170371021, 170434181, 171147601, 171284521, 171579883, 172004641, 173603561, 174413441, 175007251, 175147081, 176150179, 177285281, 177439061, 177455701, 177961639, 177991277, 180353321, 184135673, 184746889, 185504633, 186003827, 188649001, 189003781, 192227027, 194907511, 199118221, 199137121, 200791009, 203231621, 207023087, 210089303, 211099877, 221360641, 224056801, 224418401, 226525883, 226965751, 226982209, 234610291, 234755489, 239806561, 243100859, 245609041, 245795201, 247030877, 247882963, 253158751, 255866131, 256529761, 257094661, 257815277, 259179527, 264689963, 272087749, 274937851, 275946581, 276795217, 277932113, 280075277, 284301751, 284344141, 284828777, 285542711, 287375681, 289140101, 291501061, 294465761, 302784751, 302818001, 305464661, 306219377, 310701119, 312189697, 316701527, 318026801, 319287151, 324010061, 324186451, 328118281, 345701731, 351339649, 354870431, 359089091, 360783793, 364021549, 368468689, 374223991, 374654681, 375578683, 376682627, 377224051, 380182661, 382211681, 386628527, 387009737, 396106261, 400091327, 400253701, 400657277, 401005351, 401790377, 402798881, 403460429, 407282851, 410925871, 417027451, 423933241, 425612641, 429802001, 432988877, 433936141, 438424561, 439036421, 439744397, 443146057, 443969063, 448504697, 450825377, 455039027, 456780193, 461700077, 461807147, 464407883, 469721647, 475167377, 477086741, 477875231, 480053573, 480891143, 485326403, 487266991, 488248661, 488458381, 489290551, 492600439, 495101777, 504097397, 504455201, 509108081, 511121161, 511408171, 516980641, 519809701, 523827527, 527168149, 532258271, 532853441, 535702301, 540136277, 544915541, 547281851, 551313001, 557112641, 558526081, 562046627, 569720321, 570122027, 573707779, 574181327, 577647017, 583031693, 583979551, 584238563, 594301999, 598147577, 598768609, 609903521, 611463169, 611928901, 623709217, 629130449, 634002181, 634888253, 635165701, 638227127, 651861761, 657665777, 659846021, 664939277, 670042903, 670786877, 681977941, 686258627, 691455077, 691543049, 692726473, 692956819, 700190741, 704907377, 717915631, 723606391, 726357781, 729790381, 733198069, 734494801, 734498627, 738803341, 738820351, 743512001, 747587777, 748691591, 756647719, 760131139, 765947911, 768614027, 768916661, 772719947, 779566211, 780421277, 783794201, 788342777, 799500077, 808914881, 811541327, 814507541, 815496481, 818208901, 818762689, 823951171, 825393997, 829737221, 832108051, 839350363, 847053323, 847887823, 854573591, 856901267, 863097377, 865431841, 869420473, 873933527, 878330573, 879706741, 879995689, 887467621, 902096161, 922483693, 925625341, 943685959, 957600541, 961095923, 969210377, 976396961, 978920627, 982540421, 982566001, 985125077, 997540711, 999260501, 1012601251, 1015183343, 1015269391, 1032469817, 1037627051, 1050535501, 1052823241, 1054740191, 1055586377, 1058277151, 1060019221, 1064519011, 1072839941, 1085197577, 1089855841, 1105376491, 1107004579, 1112103541, 1113330077, 1113690401, 1140573601, 1157839381, 1168706449, 1171643027, 1173580127, 1177778671, 1179985921, 1189091821, 1189596241, 1189817371, 1194143443, 1198880261, 1221767831, 1226486627, 1230253133, 1232097751, 1238517649, 1260782161, 1277310731, 1280000357, 1293886001, 1295786777, 1296715741, 1298835361, 1308489103, 1309056527, 1329329041, 1344725839, 1345118777, 1352581201, 1364001113, 1371177527, 1388116201, 1389975149, 1397169091, 1401927301, 1435476803, 1437954377, 1440231941, 1447631281, 1451648021, 1469268961, 1477822433, 1479714109, 1480849831, 1490926471, 1496207809, 1524039373, 1538321777, 1540208251, 1541651627, 1554381041, 1561706327, 1569202181, 1572777551, 1613842001, 1620370127, 1637181571, 1663923827, 1669944911, 1695570841, 1749213377, 1757470643, 1769148751, 1776917381, 1783687127, 1826950127, 1831812841, 1841923841, 1885440527, 1897742027, 1912283521, 1922485969, 1942700321, 1966151713, 1976436001, 1986232877, 2025112501, 2031527803, 2044641377, 2053059121, 2054711381, 2087064527, 2105502571, 2132534777, 2141087051, 2179815377, 2184948481, 2205763129, 2207635127, 2241989381, 2261715461, 2271885527, 2273233877, 2297795249, 2305256171, 2336003647, 2346515201, 2382397877, 2387525141, 2407312577, 2411416883, 2444927627, 2470214251, 2489587361, 2509684127, 2512436189, 2525294777, 2535254027, 2563596751, 2564590757, 2630493643, 2630997541, 2641736327, 2660668877, 2673518921, 2683425889, 2767644017, 2774193827, 2776175491, 2823296341, 2832598277, 2834103827, 2837116127, 2860846721, 2887050077, 2918947111, 2970486251, 2985547447, 2986528151, 3012261281, 3054233761, 3086865941, 3174423947, 3181427027, 3197545121, 3197911001, 3223978421, 3229317529, 3234291377, 3264492481, 3295217971, 3304861061, 3316826083, 3331524377, 3332800021, 3400444277, 3435168827, 3447642571, 3453240551, 3502970551, 3525270527, 3532275919, 3558410813, 3560625077, 3596180011, 3601246277, 3625296109, 3690049277, 3717318961, 3744599777, 3747570989, 3749780509, 3752161877, 3797343377, 3804550901, 3860348777, 3881456123, 3923872577, 3966509777, 3987794201, 4068854957, 4092184277, 4141182527, 4146469181, 4188641627, 4249267577, 4265877527, 4484755277, 4550723101, 4567911571, 4601042627, 4622170877, 4639493627, 4681974527, 4701994681, 4753271251, 4998750077, 5025964481, 5134523431, 5294024413, 5321159461, 5362854071, 5388200929, 5579401229, 5981643071, 6226972861, 6294834551, 6316490251, 6454495741, 6483278869, 6641648129, 6698324881, 9316736371, 11851534697, 22200933343, 41952920641, 43015909529, 52396612381, 98831168617, 101590045727, 132258145321, 144901909651, 147624283951, 172336503151, 192900153617, 261692085691, 353833078717, 563482421611, 671092578683, 820010859361, 962298554101, 1118047771487, 1177425963001, 1470477389131, 1531650766141, 1570279465921, 1709238394189, 1964576416861, 2028221720101, 2530176740309, 3024101746009, 3157425845701, 3225594892781, 3357827162143, 3530825173441, 3763183020911, 4001021039989, 5068919516491, 5242348423051, 5324864903273, 7526211756101, 8187215713601, 8932423389707, 12328859182621, 15181669854209, 17241996257089, 18846129954107, 19894139495311, 22784540748751, 29155619954281, 29469429987317, 29805368950421, 30557495038379, 35328926825531, 54955791883981, 61697862344329, 67713696400981, 74022949251469, 82433023161451, 96908287850239, 112154241154831, 247287106198211, 247640483709109, 2038201087420801, 5723467606147861, 9433259220189751, 61561639243505213, 183571830943059491, 3407863610517545791