2^64内基于米勒罗宾素性测试的素性证明算法

_only

对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

ouukucakac

不要搞素数判定了，浪费时间！
有现成的BPSW算法，还不够好吗？

uucepekoqijew

用你的算法试试这个大合数

2887148238050771212671429597130393991977609459279722700926516024197432\
3037991527331163289831446392259419778031109293496555784189494417409338\
0561511397999942154241693397290542371100275104208013496673175515285922\
6962916775325475044445856101949404200039904432116776619949629539250452\
6987193290703735640322737012784538991261203092448414947289768854060249\
76768122077071687938121709811322297802059565867

https://bbs.emath.ac.cn/forum.ph ... 8&fromuid=14149
如何分解这个变态的卡米歇尔强伪素数？

Elishslots

汇编写的MR(n, b)

1. ;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或者xmm0USE64section .bsssection .datasection .textGLOBAL mrtestmrtest:%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 jmp1loop0:  cmp r10, 0  je jmp0  test r10, 1  jz  loop1;r11 = r11 * r9 % r8  mov rax, r11  mul r9  div r8  mov r11, rdxloop1:;r9 = r9 * r9 % r8  mov rax, r9  mul r9  div r8  mov r9, rdx  shr r10, 1  jmp loop0jmp0:; 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, r11jmp1:  sub rcx, 1  jz exit0loop3:  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 loop3exit0:      ret

复制代码

测试代码

1. extern bool mrtest(uint64_t p, uint64_t b);uint64_t ts[8][2] = {{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[i][0], ts[i][1]))      printf("mrtest(%lu, %lu) is true\n", ts[i][0], ts[i][1]);    else      printf("mrtest(%lu, %lu) is false\n", ts[i][0], ts[i][1]);}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编译通过

itimowahwafli

你还不如直接从机器语言开始编程，混合编程我不会，我连汇编都不会，我只会简单弱智的mathematica

efaugko

假设
n=2887148238050771212671429597130393991977609459279722700926516024197432\
3037991527331163289831446392259419778031109293496555784189494417409338\
0561511397999942154241693397290542371100275104208013496673175515285922\
6962916775325475044445856101949404200039904432116776619949629539250452\
6987193290703735640322737012784538991261203092448414947289768854060249\
76768122077071687938121709811322297802059565867

那么Log[2, Log[2, n]]，对2取两次对数，结果是10.3631，
但是这个n，能通过1到307的强伪素数的测试！

Jeninslots

那你二次域给我看看呀

ahqhegudiz

https://bbs.emath.ac.cn/forum.ph ... 3&fromuid=14149

用lucas U lucas V就行了！

oabipalehov

各一次基2，3的MR
然后卢卡斯测试或者二次域测试，我有时间比较下哪个快

hozewovaxemam

整天研究素数判定，难道你还想搞出个大新闻？？？？？？？