Name

number_probableprime — Check if a number is a probable prime.

Calling Sequence

   isprime = number_probableprime ( n )
   isprime = number_probableprime ( n , s )
   isprime = number_probableprime ( n , s , verbose )
   
   

Parameters

n :

a 1x1 matrix of floating point integers, must be positive, the positive integer to test for primality

s :

a 1x1 matrix of floating point integers, the number of loops in the test for primality (default 50)

verbose :

a 1-by-1 matrix of booleans, set to true to display messages (default verbose=%f)

isprime :

a 1x1 matrix of booleans

Description

Returns %f if the number is a composite. Returns %t if the number is a probable prime. Uses Miller-Rabin randomized primality test.

Uses random integers from the grand function (option "uin").

Examples

// Check for actual primes
number_probableprime ( 7 ) // %t
number_probableprime ( 5 ) // %t
number_probableprime ( 5 , 3 ) // %t

// Check for composite numbers
number_probableprime ( 10 ) // %f
number_probableprime ( 20 ) // %f

// Check for pseudo-primes : while pseudo prime does not detect that these numbers
// are composite, probable prime does it perfectly.
number_probableprime ( 341 ) // %f
number_probableprime ( 561 ) // %f
number_probableprime ( 645 ) // %f
number_probableprime ( 1105 ) // %f

// Test verbose option
number_probableprime ( 10001 , [] , %t );

// Test s option
number_probableprime ( 10001 , 10 , %t );

// This function may fail if intermediate integers get too large.
// An error is generated:
number_probableprime ( 4432676798593 )

   

Bibliography

"Introduction to algorithms", Cormen, Leiserson, Rivest, Stein, 2nd edition

Authors

Copyright (C) 2009 - 2010 - DIGITEO - Michael Baudin