AKS Primes algorithm in Python

python algorithm primes

1,723

Quick answer: no, the AKS test is not the fastest way to test primality. There are much much faster primality tests that either assume the (generalized) Riemann hypothesis and/or are randomized. (E.g. Miller-Rabin is fast and simple to implement.) The real breakthrough of the paper was theoretical, proving that a deterministic polynomial-time algorithm exists for testing primality, without assuming the GRH or other unproved conjectures.

That said, if you want to understand and implement it, Scott Aaronson's short article might help. It doesn't go into all the details, but you can start at page 10 of 12, and it gives enough. :-) There is also a list of implementations (mostly in C++) here.

Also, for optimization and improvements (by several orders of magnitude), you might want to look at this report, or (older) Crandall and Papadopoulos's report, or (older still) Daniel J Bernstein's report. All of them have fairly detailed pseudo-code that lends itself well to implementation.

1,723

Author by

Ablivion

Updated on July 24, 2022

Comments

Ablivion almost 2 years

I have a small fan website dedicated to a certain game. Now in that game there are two live events that reset after some period of time. First one resets every 18h and the other one resets every week (on the same day at the same time). I have been working on a script to put on the site to show when the next event reset is. I have made it work for the most part:

timer.html

<!DOCTYPE html>
<html>
<head>
<link rel="stylesheet" type="text/css" href="style.css">
<script src="timer.js" type="text/javascript"></script>
<script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.8.2/jquery.min.js"></script>
</head>
<body>

<div id="daily">
  <p ></p>
</div>

<div id="weekly">
  <p ></p>
</div>

</body>
</html>

style.css

@import url(http://fonts.googleapis.com/css?family=Lato:100,400);
#daily, #weekly {
  background: #333;
  font-family: 'Lato', sans-serif;
  text-align: center;
  color: #eee;
  text-shadow: 1px 1px 5px black;
  padding: 1rem 0;
  font-size: 3rem;
  border: 1px solid #000;
}

timer.js

setInterval(function time(){

// Get strating and current date
var startDate = new Date("January 7, 2016 07:00:00");
var currentDate = new Date();

// Calcualte time passed since the start
var timePassed = currentDate.getTime() - startDate.getTime();
var convertToSeconds = Math.floor(timePassed / 1000 );
var convertToMinutes = Math.floor(convertToSeconds / 60);
var convertToHours = Math.floor(convertToMinutes / 60);
var convertToDays = Math.floor(convertToHours / 24);

// Calculate time since last daily (18h) reset
var lastResetSeconds = convertToSeconds % 60;
var lastResetMinutes = convertToMinutes % 60;
var lastResetHoursDaily = convertToHours % 18;

// Calculate time since last weekly (7d) reset
var lastResetHoursWeekly = convertToHours % 24;
var lastResetDay = convertToDays % 7;

// Calculate remaining time until next daily (18h) reset
var remainingSeconds = 59 - lastResetSeconds;
var remainingMinutes = 59 - lastResetMinutes;
var remainingHoursDaily = 17 - lastResetHoursDaily;

// Calculate remaining time until next weekly (7d) reset
var remainingHoursWeekly = 23 - lastResetHoursWeekly;
var remainingDays = 6 - lastResetDay;

// If any of the variables is only a single digit number, then add 0 before
if((remainingSeconds + '').length == 1){
  remainingSeconds = '0' + remainingSeconds;
}
if((remainingMinutes + '').length == 1){
  remainingMinutes = '0' + remainingMinutes;
}
if((remainingHoursDaily + '').length == 1){
  remainingHoursDaily = '0' + remainingHoursDaily;
}
if((remainingHoursWeekly + '').length == 1){
  remainingHoursWeekly = '0' + remainingHoursWeekly;
}
if((remainingDays + '').length == 1){
  remainingDays = '0' + remainingDays;
}

// Print
jQuery('#daily p').html(remainingHoursDaily+':'+remainingMinutes+':'+remainingSeconds)
jQuery('#weekly p').html(remainingDays+':'+remainingHoursWeekly+':'+remainingMinutes+':'+remainingSeconds)
}, 1000);

Timezone Problem

JS calculates client side time and not server side and this is a problem. This is an event that started on a certain date at certain time in PDT zone, and has restarted itself every 18h. So when I view this page I get time calculated from starting and current date BUT from my timezone and not the one from the server.

What I'm looking for here is that starting date and current date are used from server and not the client. Now, I'm aware that JS is client side run, so what I need is a workaround.

I then attempted something with php which resulted in same problem as remaining time seems to be far off. To add further to the list of problems, the jQuery no longer counts down, instead it just shows remaining time it got while loading script/page.

timer.php

<!DOCTYPE html>
<html>
<head>
<link rel="stylesheet" type="text/css" href="style.css">
<script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.8.2/jquery.min.js"></script>
</head>
<body>
<?php

    date_default_timezone_set('America/Los_Angeles');
    $rawDateStart = date('F j, Y H:i:s', date_timestamp_get(DateTime::createFromFormat('F j, Y H:i:s', 'January 7, 2016 07:00:00')));
    $rawDateCurrent = date('F j, Y H:i:s');
?>

<script>
setInterval(function time(){

    // Get strating and current date
    //var startDate = new Date("January 7, 2016 07:00:00");
    //var currentDate = new Date();
    var startDate = new Date("<? echo $rawDateStart; ?>");
    var currentDate = new Date("<? echo $rawDateCurrent; ?>");

    // Calcualte time passed since the start
    var timePassed = currentDate.getTime() - startDate.getTime();
    var convertToSeconds = Math.floor(timePassed / 1000 );
    var convertToMinutes = Math.floor(convertToSeconds / 60);
    var convertToHours = Math.floor(convertToMinutes / 60);
    var convertToDays = Math.floor(convertToHours / 24);

    // Calculate time since last daily (18h) reset
    var lastResetSeconds = convertToSeconds % 60;
    var lastResetMinutes = convertToMinutes % 60;
    var lastResetHoursDaily = convertToHours % 18;

    // Calculate time since last weekly (7d) reset
    var lastResetHoursWeekly = convertToHours % 24;
    var lastResetDay = convertToDays % 7;

    // Calculate remaining time until next daily (18h) reset
    var remainingSeconds = 59 - lastResetSeconds;
    var remainingMinutes = 59 - lastResetMinutes;
    var remainingHoursDaily = 17 - lastResetHoursDaily;

    // Calculate remaining time until next weekly (7d) reset
    var remainingHoursWeekly = 23 - lastResetHoursWeekly;
    var remainingDays = 6 - lastResetDay;

    // If any of the variables is only a single digit number, then add 0 before
    if((remainingSeconds + '').length == 1){
      remainingSeconds = '0' + remainingSeconds;
    }
    if((remainingMinutes + '').length == 1){
      remainingMinutes = '0' + remainingMinutes;
    }
    if((remainingHoursDaily + '').length == 1){
      remainingHoursDaily = '0' + remainingHoursDaily;
    }
    if((remainingHoursWeekly + '').length == 1){
      remainingHoursWeekly = '0' + remainingHoursWeekly;
    }
    if((remainingDays + '').length == 1){
      remainingDays = '0' + remainingDays;
    }

    // Print
    jQuery('#daily p').html(remainingHoursDaily+':'+remainingMinutes+':'+remainingSeconds)
    jQuery('#weekly p').html(remainingDays+':'+remainingHoursWeekly+':'+remainingMinutes+':'+remainingSeconds)
}, 1000);
</script>

<div id="daily"><p ></p></div>
<div id="weekly"><p ></p></div>

</body>
</html>

So I'm stuck and without any ideas how to proceed. Any pointers would be welcome. I'm honestly having hard time with time / date stuff.

sidgeon smythe about 14 years

Update: Another good exposition of the mathematics,by Terence Tao, here: terrytao.wordpress.com/2009/08/11/the-aks-primality-test
Progo about 10 years

The AKS-Test isn't the fastest way, but it is a the first fool-proof test for primes.
sidgeon smythe about 10 years

@Progo: More precisely, it's the first test which we can prove is fool-proof and polynomial-time. There are other tests which we strongly believe are actually perfectly fool-proof (e.g. because it is possible to prove them assuming strongly-believed conjectures like the Riemann Hypothesis), and there are also other tests which we can prove are perfectly fool-proof, and which almost invariably run fast, but which we can't prove are polynomial-time. The breakthrough of the AKS was doing both.
sidgeon smythe about 9 years

This is not the AKS algorithm; this is an exponential-time algorithm that implements the elementary idea behind the AKS algorithm with none of the ideas that makes it polynomial-time.
DanaJ almost 9 years

@Progo, clearly you watched the numberphile video, which is very misleading. It is not the fastest way, isn't the first fool-proof test, isn't the fastest fool-proof test, etc. It is deterministic polynomial time, which we didn't have before without assuming the ERH. We had (and still use today) APR-CL which is effectively polynomial time for any input we will be computing. We had, and still use, ECPP which is expected polynomial time (but could run slowly due to randomness). Both are "fool-proof" methods and are much faster.
Ablivion over 8 years

Sweet! That worked, thank you. EDIT: The only minor error is adding 0 to wrong value (after : ), I just switched to add it to correct value. (after ?)
Vince over 8 years

@Ablivion Haha, you beat me to it -- I just updated the answer to fix that issue!