Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

Fast but long, partly tabular version of deterministic Miller-Rabin up to 2^64 #1561

Open
@Artoria2e5

Description

@Artoria2e5

The website for helping people select few Miller-Rabin bases,https://miller-rabin.appspot.com/, has a small section on "Hashing". There a hash function is used to link the input number to a certain base (or set of bases) where it is known beforehand that all numbers that can hash to this bucket are not a pseudoprime of this base. In other words, dynamic base selection to reduce the number of bases used.

The current state of this work is on Berg's website,https://www.techneon.com/. I quote from the website:

These primality tests extend Steve Worley's 32 bit primality test. They improve onJim Sinclair's test that uses 7 SPRP tests. 32 bit numbers are checked with a single SPRP test, two are used for 49 bit numbers, and three for 64 bit numbers.

Numbers under 2^32 can be tested using the SPRP bases in: [is.prime.32.base.data](https://www.techneon.com/download/is.prime.32.base.data)Numbers from 2^32 to 2^64 can be tested using the base pairs in: [is.prime.64.base.data](https://www.techneon.com/download/is.prime.64.base.data)

[...]

The sprp test can be substantially sped up with negligible overhead by interleaving it with trial division over small primes. A modulus by a small prime is computed in each iteration of the loop for Base ^ D mod N.

Numbers with 49 or fewer bits fit in a floating point double. The modulus can be computed by multiplying by the reciprocal of small primes that are pre-computed and stored in an array. Division is avoided and processors can perform floating point operations in parallel with integer operations.

I don't know who needs this thing (for one thing, nobody is memorizing this!), but if anyone really wants that bit of speed, adding a small link would tell them where to look.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions


      [8]ページ先頭

      ©2009-2025 Movatter.jp