数学研发论坛

 找回密码
 欢迎注册
查看: 137|回复: 2

[求助] 为什么算了很久才得到雅克比符号等于-1?

[复制链接]
发表于 2022-9-9 14:15:10 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
BPSW算法中,选择d=5,-7,9,-11,13,-15,17,-19,21,-23,25...从这个数列中选择第一个雅克比符号等于-1的d,d相对于n的雅克比符号
n=145823#+1(63142位大整数)

其中8#+1=7*5*3*2+1,其中8#表示小于等于8的所有的素数的乘积,

  1. Clear["Global`*"];
  2. m=145823;
  3. n=Times@@Prime@Range@PrimePi[m]+1;(*小于等于m以下的所有的素数的乘积*)
  4. d=5;(*初始判别式的值*)
  5. c=1;(*统计次数,第几个判别式的值*)
  6. Do[js=JacobiSymbol[d,n];(*计算雅克比符号*)
  7.    If[js==-1,Print[{d,(1-d)/4,c}];Break[]];(*如果雅克比符号等于-1,则输出相关结果*)
  8.    If[d>0,d=(-1)*d-2,d=(-1)*d+2];(*不等于-1的处理办法*)
  9.    c=c+1,(*增加1*)
  10. {k,1,10^6}]
复制代码


运算结果:
{145829,-36457,72913}
此处,145829似乎是145823的下一个素数。
此处两个提问:
1、为什么雅克比符号运算了那么多次?
2、145829似乎是145823的下一个素数,这种情况是偶然的,还是必然的?如果是必然的,那么怎么证明?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-9-9 14:17:56 | 显示全部楼层
n=18523#+1  则输出结果{-18539,4635,9268}
18539是18523的下一个素数!我感觉具有必然性
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-9-17 11:20:54 来自手机 | 显示全部楼层
根据二次互反律,相当于要求n不是d的平方剩余,由此得出d不能所有素因子都小于n-1的最大素因子
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2022-10-3 07:10 , Processed in 0.115822 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表