2^64内基于米勒罗宾素性测试的素性证明算法
对n进行基b的米勒罗宾素性测试定义为MR(n, b)算法步骤
1、首先进行基 2 的 MR(n, 2)，
如果测试失败，返回 n 是合数，结束
否则，继续 2
2、对 n 求 s = $|log_2(log_2(n))|$
3、找到最小正整数 $t_0$ 满足 $t_0^s \ge n$
4、对于大于等于 $t_0$ 的连续素数 t 执行 s + 3 次 MR(n, t)，
如果某次测试失败，返回 n 是合数，结束
如果全部通过，返回 n 是素数，结束
此时，只有 214021506061375741 失败
如果改成 $t_0$ 开始连续整数，则有2个失败
9450361108305253
1578072131184991861 不要搞素数判定了，浪费时间！
有现成的BPSW算法，还不够好吗？ 用你的算法试试这个大合数
2887148238050771212671429597130393991977609459279722700926516024197432\
3037991527331163289831446392259419778031109293496555784189494417409338\
0561511397999942154241693397290542371100275104208013496673175515285922\
6962916775325475044445856101949404200039904432116776619949629539250452\
6987193290703735640322737012784538991261203092448414947289768854060249\
76768122077071687938121709811322297802059565867
https://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=17388&fromuid=14149
如何分解这个变态的卡米歇尔强伪素数？ 汇编写的MR(n, b)
;bool mrtest(uint64_t p, uint64_t b)
;win64下，前4个参数如果是整数或者指针保存到rcx, rdx, r8, r9
;如果是浮点数，保存到xmm0, xmm1, xmm2, xmm3
;如果是混合参数，则按照对应位置选择寄存器
;多于4个的参数从右到左压栈，同时栈顶为前4个参数保留32字节影子空间
;函数内可以自由使用rax, rcx, rdx, r8, r9, r10, r11, xmm0-xmm5
;其他寄存器需要使用时候，则要保证在退出函数时恢复值
;返回值保存在rax内，如果是浮点数保存在xmm0
;linux, FreeBSD, MacOS等64位系统则遵循另外一个规则
;前6个参数保存到rdi, rsi, rdx, rcx, r8, r9,
;浮点数则保存到xmm0-xmm5
;多于6个从右到左依次压栈，没有影子空间，
;函数内可以自由使用rax, rcx, rdx, rsi, rdi, r8, r9, r10, r11
;返回值保存到rax或者xmm0
USE64
section .bss
section .data
section .text
GLOBAL mrtest
mrtest:
%ifidn __OUTPUT_FORMAT__, win64
mov r8, rcx
mov r9, rdx
%else
mov r8, rdi
mov r9, rsi
%endif
;r8 = p, r9 = b
mov r10, r8
mov rax, 1
movq xmm0, rax
movq xmm3, r8
;xmm3 = p-1
psubq xmm3, xmm0
pxor xmm2, xmm2
;xmm2 = 1
paddq xmm2, xmm0
sub r10, 1
;r10 = p - 1
bsf rcx, r10
;rcx = k
shr r10, cl
;r10 = m, p - 1 = m * 2^k
mov r11, 1
cmp r10, 1
je jmp1
loop0:
cmp r10, 0
je jmp0
test r10, 1
jzloop1
;r11 = r11 * r9 % r8
mov rax, r11
mul r9
div r8
mov r11, rdx
loop1:
;r9 = r9 * r9 % r8
mov rax, r9
mul r9
div r8
mov r9, rdx
shr r10, 1
jmp loop0
jmp0:
; xmm0 = (r11 == 1 || r11 == p-1)? -11 : 0
movq xmm0, r11
movq xmm1, r11
pcmpeqq xmm0, xmm2;xmm0=r11 == 1?(-1):0
pcmpeqq xmm1, xmm3;xmm1=r11 == (p-1)?(-1):0
por xmm0, xmm1
;if (rax = -xmm0 == 1) then exit
movq rax, xmm0
neg rax
cmp rax, 1
je exit0
mov r9, r11
jmp1:
sub rcx, 1
jz exit0
loop3:
mov rax, r9
mul r9
div r8
mov r9, rdx
;xmm1 = r9 == p-1? (-1):0
movq xmm1, r9
pcmpeqq xmm1, xmm3
movq rax, xmm1
neg rax
cmp rax, 1
je exit0
sub rcx, 1
jnz loop3
exit0:
ret
测试代码
extern bool mrtest(uint64_t p, uint64_t b);
uint64_t ts = {{257,2},{255,2}, {2047, 2},{121, 3},
{10095020520187, 2}, {581130733, 3}, {55031295157, 234587},
{55031295179, 234587}};
void testmrtest( void )
{
for (uint64_t i = 0; i < 8; i ++)
if (mrtest(ts, ts))
printf("mrtest(%lu, %lu) is true\n", ts, ts);
else
printf("mrtest(%lu, %lu) is false\n", ts, ts);
}
int main( void )
{
testmrtest();
}
假设汇编名为 mr.asm, C代码 mrtest.c
linux下
nasm -f elf64 mr.asm -o mr.o
gcc mrtest.c mr.o -o mrtest
windows下
nasm -f win64 mr.asm
gcc mrtest.c mr.obj -o mrtest
即可生成测试程序
汇编代码也可以用yasm编译通过
无心人 发表于 2023-4-25 10:01
汇编写的MR(n, b)
其实我主要是为了搞明白64汇编怎么和C语言混合编程
你还不如直接从机器语言开始编程，混合编程我不会，我连汇编都不会，我只会简单弱智的mathematica 无心人 发表于 2023-4-25 10:01
汇编写的MR(n, b)
假设
n=2887148238050771212671429597130393991977609459279722700926516024197432\
3037991527331163289831446392259419778031109293496555784189494417409338\
0561511397999942154241693397290542371100275104208013496673175515285922\
6962916775325475044445856101949404200039904432116776619949629539250452\
6987193290703735640322737012784538991261203092448414947289768854060249\
76768122077071687938121709811322297802059565867
那么Log]，对2取两次对数，结果是10.3631，
但是这个n，能通过1到307的强伪素数的测试！ 无心人 发表于 2023-4-25 10:01
汇编写的MR(n, b)
那你二次域给我看看呀 nyy 发表于 2023-4-25 13:31
假设
n=2887148238050771212671429597130393991977609459279722700926516024197432\
30379915273311632 ...
https://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=18553&fromuid=14149
用lucas U lucas V就行了！ 各一次基2，3的MR
然后卢卡斯测试或者二次域测试，我有时间比较下哪个快 无心人 发表于 2023-4-25 16:08
各一次基2，3的MR
然后卢卡斯测试或者二次域测试，我有时间比较下哪个快
整天研究素数判定，难道你还想搞出个大新闻？？？？？？？
页:
[1]
2