SQL Server Magazine

You must log on before posting a comment.

If you don't have a username & password, please register now.

/* Hi Itzik,

Here is a function that should handle integers up to one-half the maximum bigint. It's designed to be efficient for very large inputs. For example, it tests the odd integers between 422337203685477581 and 422337203685477691, finding the 7 primes, in about a second on a modest machine.

It is based on the Miller-Rabin test for strong pseudoprimality, and it uses pubished efficient sets of bases useful for this test (see (http://math.crg4.com/primes.html).

This will be much slower than other approaches for small inputs (< 10^9, say), and I expect to lose points for that, perhaps many! I hope the function is correct. I didn't do a great deal of testing.

Steve Kass skass@drew.edu http://www.stevekass.com

Note: I will post the required auxiliary functions in a second comment, because I can only post 2000 characters here. */

-- requires auxiliary functions posted separately create function fn_isprime( @n bigint ) returns bit as begin declare @result bit; if right(@n,1) in ('0','2','4','6','8','5') return 0; if @n%3=0 return 0; if @n%7=0 return 0; if @n%11=0 return 0; if @n%13=0 return 0; set @result = dbo.RabinPseudoPrime (@n, 2); if @result = 0 or @n < 2047 return @result; set @result = dbo.RabinPseudoPrime (@n, 3); if @result = 0 or @n < 1373653 return @result; set @result = dbo.RabinPseudoPrime (@n, 5); if @result = 0 or @n < 25326001 return @result; set @result = dbo.RabinPseudoPrime (@n, 7); if @result = 0 or @n < 3215031751 return @result; if dbo.RabinPseudoPrime(@n,61) = 0 return 0; return dbo.RabinPseudoPrime(@n,25251) return @result; end;

stevekass- October 30, 2007

Article Rating 5 out of 5

Itzik,

Here are the auxiliary functions. Unfortunately, cut-and-paste from SQL Server Management Studio destroyed all the formatting in the previous comment, and I expect that will happen here. If you can fix it, great - otherwise, my apologies to readers.

Steve Kass skass@drew.edu http://www.stevekass.com

create function modMult( @f1 bigint, @f2 bigint, @modulus bigint ) returns bigint as begin declare @result bigint; set @result = 0; while @f2 > 0 begin if @f2 % 2 = 1 set @result = (@result + @f1)%@modulus set @f2 = @f2/2; set @f1 = (@f1 + @f1) % @modulus; end; return @result; end; go

create function modPower( @base bigint, @exponent bigint, @modulus bigint ) returns bigint as begin declare @result bigint; set @result = 1; while @exponent > 0 begin if @exponent%2 = 1 set @result = dbo.modMult(@result,@base,@modulus); set @exponent = @exponent / 2; set @base = dbo.modMult(@base,@base,@modulus); end; return @result; end go

create function RabinPseudoPrime( @n bigint, @witness bigint ) returns bit as begin declare @s int; set @s = 0; declare @d bigint; set @d = @n - 1; while @d%2 = 0 begin set @s = @s + 1; set @d = @d/2; end if dbo.modPower(@witness,@d,@n) = 1 return 1; while @d <= (@n-1)/2 begin if dbo.modPower(@witness,@d,@n) = @n-1 return 1; set @d = @d*2; end; return 0; end;

stevekass- October 30, 2007

Article Rating 5 out of 5

Steve's function performs excellent but it needs an extra line just after the first declare inside fn_IsPrime.

if @n in (2,3,5,7,11,13) return 1;

jmorrison- November 07, 2007

Article Rating 5 out of 5

Not that it matters in practice, but isn't Miller-Rabin test either undeterministic or conditional?

multisoft- November 09, 2007

Article Rating 4 out of 5

Yes, it is only a test but steve choise parameters to grant the test returns the exact results for numbers as bigint.

I worked about this problem but I think is not possible to create a solution best of Steve Kass solution.

Steve, you are a genius.

marcello.

info@epomops.it- November 14, 2007

Article Rating 5 out of 5