[Octave-bug-tracker] [bug #61312] Extending isprime() with Miller-Rabin test

[Arun Giridhar]

URL:
  <https://savannah.gnu.org/bugs/?61312>

                 Summary: Extending isprime() with Miller-Rabin test
                 Project: GNU Octave
            Submitted by: arungiridhar
            Submitted on: Fri 08 Oct 2021 06:43:58 PM EDT
                Category: Octave Function
                Severity: 3 - Normal
                Priority: 5 - Normal
              Item Group: Performance
                  Status: None
             Assigned to: None
         Originator Name: 
        Originator Email: 
             Open/Closed: Open
                 Release: dev
         Discussion Lock: Any
        Operating System: Any

    _______________________________________________________

Details:

I have attempted to extend isprime() to go to the full range of 64-bit
integers. Currently isprime() tends to slow down for any input over about 1e15
with the prime generation and direct division technique, so I've implemented a
Miller-Rabin primality test for larger n, up to 2^64-1.

Please test the attached function and test/benchmark script. For development
it's temporarily named isprime2().

Feedback solicited, please!



    _______________________________________________________

File Attachments:


-------------------------------------------------------
Date: Fri 08 Oct 2021 06:43:58 PM EDT  Name: primality_benchmark.m  Size: 472B
  By: arungiridhar

<http://savannah.gnu.org/bugs/download.php?file_id=52077>
-------------------------------------------------------
Date: Fri 08 Oct 2021 06:43:58 PM EDT  Name: isprime2.m  Size: 11KiB   By:
arungiridhar

<http://savannah.gnu.org/bugs/download.php?file_id=52078>

    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?61312>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/