It is based on the Miller-Rabin
It is
based on the Miller-Rabin test for strong pseudoprimality, and it
uses pubished efficient sets of bases for primality testing based
on this
test [http://math.crg4.com/primes.html].”
-- Solution by Steve Kass
if object_id('dbo.modMult') is not null
drop function dbo.modMult;
go
create function
dbo.modMult(
@f1 bigint,
@f2 bigint,
@modulus bigint
) returns bigint as begin
declare
@result bigint;
set
@result
= 0;
--declare @sign int;
--set @sign = sign(@f1)*sign(@f2);
--set @f1 = abs(@f1);
--set @f2 = abs(@f2);
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--*@sign;
end;
go
if object_id('dbo.modPower') is not null
drop function dbo.modPower;
go
create function
dbo.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
if object_id('dbo.RabinPseudoPrime') is not null
drop function dbo.RabinPseudoPrime;
go
create function
dbo.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;
go
if object_id('dbo.fn_isprimeSK') is not null
drop function dbo.fn_isprimeSK;
go
create function
dbo.fn_isprimeSK(
@n bigint
) returns bit as begin
declare
@result bit;
if @n < 17
if
@n in (2, 3, 5, 7, 11, 13) return 1 else return 0;
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;
Again, as far as I can tell, existing fast deterministic
techniques are
suited for iterative/recursive implementations and not set-based ones.
An implementation of iterative/recursive algorithms would probably be
much faster with CLR code compared to T-SQL code.
You can find more details about fast deterministic tests
here:
http://en.wikipedia.org/wiki/Primality_test, and more details about the
Miller-Rabin test here:
http://en.wikipedia.org/wiki/Miller-
Rabin_primality_test.
Cheers,
--
BG
End of Article
Prev. page
1
2
3
4
5
6
[7]
next page -->
