Mathrelated

Tag: probableprime

  • Ruling out Pseudoprimes – part 5

    In this post we continue through the OEIS 047713 Pseudoprimes tabulating the results of power (p-1)/4 as a filter

    Table of Pseudoprimes starting at 3094273
    Table of Pseudoprimes starting at 4259905
    Counts and conclusions based on 60 pseudoprime table

  • Ruling out Pseudoprimes – part 4

    In this post we continue through the OEIS 047713 Pseudoprimes tabulating the results of power (p-1)/4 as a filter

    Table of pseudoprimes starting at 1678541
    Table of pseudoprimes starting at 2232865
    Counts and conclusions based on 60 pseudoprime table

  • Ruling out Pseudoprimes – part 3

    In this post we continue through the OEIS 047713 Pseudoprimes tabulating the results of power (p-1)/4 as a filter

    Table of Pseudoprimes starting at 745889
    Table of Pseudoprimes starting at 1194649
    counts and conclusions based on the 60 Pseudoprimes tested

  • Ruling out Pseudoprimes – part 2

    In this post we continue through the OEIS 047713 Pseudoprimes tabulating the results of power (p-1)/4 as a filter

    Table of Pseudoprimes starting at 113201

    .

    Table of Pseudoprimes starting at 357761
    Summary of counts and conclusions based on the 60 items tested

  • Proving Proth number prime using Euler – extra step

    In the previous post we offered a partial answer to proving a Proth Number is prime

    The result would be a probable prime to base 2.

    .

    Table of pseudoprimes with (p-1)/4 test result

    74665 is not a Proth Number. Is 74665 a strong Euler-Jacobi Pseudoprime?

    Of the 37 initial terms in OEIS sequence A047713 we found the following:

    One Pseudoprime passed the filter – 74665

    Three were Incalculable as p-1 not divisible by 4

    Five were marked ‘not applicable’ as we can only apply our filter when (2/p)=1

    One in twenty-nine passed the filter which means we eliminated 96% of the Pseudoprimes using this extra filter.

    If you count the 8 for which our filter could not be used then we still eliminated 3/4 of the Pseudoprimes.

    For the conjecture at the top of this page, we would always be dealing with (p-1) divisible by 8 and 2^((p-1)/2) = 1 mod p

    So our filter would likely achieve near the 96% we achieved here.

    Having amended the previous post, this filter is already incorporated into our prime test.

    If reading this post has got you interested in Probable Prime theory then the following resources might offer some further reading:

  • Mathematical discovery

    There are many ways that Mathematical discovery can happen.

    Doing an Undergraduate degree or Masters or PhD are ways that discoveries can be made.

    Working in Algebra for many years and asking “what if” is another way.

    My discovery, depending on your point of view, is one or more of the following:

    • Discovered a strong probable prime or ‘is prime’ test for a particular set
    • “fixed the b” so same base used all the time for a prime test of Proth numbers
    • Discovered a set in which a probable prime test behaves strongly.

    Thought it worth describing the process that has allowed that to happen and will talk subjectively about that next.
    ( Do jump ahead to the Conjectures at the bottom of this post if you are interested more in that )

    Have spent many years working in the set

    1+(−1+2t)∗(2t+1)1+(-1+2^t)*(2^{t+1})

    Documented lots of algebraic observations, and through them, was able to come up with an order conjecture involving a least common multiple.

    Nothing too exciting so far.

    Through thinking about order of two elements in particular, began to see the importance of thinking lengthwise about things with decreasing and increasing values of t.

    This is in contrast to thinking about isomorphism primarily, where we tend to view order as an important separator and then move laterally between [groups].


    Went so far as to propose a new definition “sturdy element” to facilitate this thinking.

    Tabulated [a lot] of group examples using those elements.
    ( See other posts on this site )

    Adjusted the set definition slightly from

    1+(−1+2t)∗(2t+1)1+(-1+2^t)*(2^{t+1})

    to nearby sets

    This was a key step

    Broke away from considering only sets we can describe as Proth numbers and considered other sets.

    Still thinking about order and patterns and came up with some new conjectures.

    To try and add a few chapters to my draft book, returned to sets of Proth numbers but considered slightly different powers.

    This was another key step.

    During this time was always asking “what if” and “suppose” type questions of what I was seeing.


    This supposing and enquiring was another key step.


    Spotted something interesting when working with groups in set

    1+(−1+2t)∗(2t+3)1+(-1+2^t)*(2^{t+3})

    Factored the order of a couple of groups to see if there was anything to see.


    Made a supposition and tested it for a couple of examples.


    Found that the pattern did not apply in all cases.


    Asked the question did it only apply to primes.


    There was the discovery [ see conjecture next ]

    Created a script to test things out.


    Used a computer algebra package to run the script to see it work with larger examples.


    The largest prime found [9769 digits] using this probable prime test as a filter is next.

    1+(−1+216224)×(216227)  is  Prime1+(-1+2^{16224})×(2^{16227}) ~ ~ is ~ ~ Prime

    Looked for a further set with something that looked algebraic

    The largest prime found [386 digits] using this probable prime test as a filter is next.

    1+(1+2639)×(2642)  is  Prime1+(1+2^{639})×(2^{642}) ~ ~ is ~ ~ Prime

    The early build up to my discovery involved tabulating over 100 groups.

    This tabulation is documented in the early chapters of my (draft) book.

  • Strong probable prime test using element 2 and set 1+(1+2^t)×(2^(t+3))

    Consider the Proth space

    1+(1+2t)∗(2t+3)1+(1+2^t)*(2^{t+3})

    Using the above conjecture we have established the following

    1+(1+2639)×(2642)  is  Prime1+(1+2^{639})×(2^{642}) ~ ~ is ~ ~ Prime

    By tabulating order of groups next we provide examples where order follows the conjecture and other examples where the Proth number used is composite.

    We will be using generating element 2

    When t=3 we have P=1+9×64 and the set of elements modulo P is a multiplicative group.


    The subgroup generated by 2 has 144 elements

    Order is (2^4)×(1+2^3) so we are a [probable] prime.

    The elements in TPc144 are as shown next
    { 2, 4, 8, 16, 32, 64, 128, 256, 512, 447,
    317, 57, 114, 228, 456, 335, 93, 186, 372, 167,
    334, 91, 182, 364, 151, 302, 27, 54, 108, 216,
    432, 287, 574, 571, 565, 553, 529, 481, 385, 193,
    386, 195, 390, 203, 406, 235, 470, 363, 149, 298,
    19, 38, 76, 152, 304, 31, 62, 124, 248, 496,
    415, 253, 506, 435, 293, 9, 18, 36, 72, 144,
    288, -1, 575, 573, 569, 561, 545, 513, 449, 321,
    65, 130, 260, 520, 463, 349, 121, 242, 484, 391,
    205, 410, 243, 486, 395, 213, 426, 275, 550, 523,
    469, 361, 145, 290, 3, 6, 12, 24, 48, 96,
    192, 384, 191, 382, 187, 374, 171, 342, 107, 214,
    428, 279, 558, 539, 501, 425, 273, 546, 515, 453,
    329, 81, 162, 324, 71, 142, 284, 568, 559, 541,
    505, 433, 289, 1 }

    Next we look at 2177=7*311 and see order is 465 so does not follow the rule established in the conjecture as the Proth number is composite.

    For 2177 from t=4 the 465 elements in TPc465 are not tabulated here
    For 8449 from t=5 the 840 elements in TPc840 are not tabulated here
    For 33281 from t=6 the 7953 elements in TPc7953 are not tabulated here
    For 132097 from t=7 the 6972 elements in TPc6972 are not tabulated here
    For 526337 from t=8 the 17688 elements in TPc17688 are not tabulated here
    For 2101249 from t=9 the 525312 elements in TPc525312 are not tabulated here
    For 8396801 from t=10 the 298680 elements in TPc298680 are not tabulated here

    A script based on the conjecture is shown next

    Running that script for t to 500 gives some small examples that fit with the conjecture

    A question that applies to all such searches once t becomes large is whether the primes exist.

    This is an open question not answered here.

    Do adjust the value for starter to search from the starting t value you require and run the script in Pari/GP or adapt it for your favoured computer algebra package.