...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Mathematics of computation >Two kinds of strong pseudoprimes up to 10(36)
【24h】

Two kinds of strong pseudoprimes up to 10(36)

机译：两种强伪素数，最高可达10（36）

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Let n > 1 be an odd composite integer. Write n-1 = 2(s)d with d odd. If either b(d) = 1 mod n or b(2rd) = -1 mod n for some r = 0, 1,..., s-1, then we say that n is a strong pseudoprime to base b, or spsp(b) for short. Define psi(t) to be the smallest strong pseudoprime to all the first t prime bases. If we know the exact value of psi t, we will have, for integers n < psi(t), a deterministic efficient primality testing algorithm which is easy to implement. Thanks to Pomerance et al. and Jaeschke, the psi(t) are known for 1 <= t <= 8. Conjectured values of psi(9),...,psi(12) were given by us in our previous papers (Math. Comp. 72 (2003), 2085-2097; 74 (2005), 1009-1024). The main purpose of this paper is to give exact values of psi'(t) for 13 <= t <= 19; to give a lower bound of psi'(20) : psi'(20) > 10(36) ; and to give reasons and numerical evidence of K2- and C-3- spsp's < 10(36) to support the following conjecture: psi(t) = psi'(t) < psi''(t) for any t >= 12, where psi(t) (resp. psi"(t)) (i)s the smallest K2- (resp. C-3-) strong pseudoprime to all the first t prime bases. For this purpose we describe procedures for computing and enumerating the two kinds of spsp's < 10(36) to the first 9 prime bases. The entire calculation took about 4000 hours on a PC Pentium IV/ 1.8GHz. (Recall that a K2- spsp is an spsp of the form: n = pq with p, q primes and q - 1 = 2(p - 1); and that a C-3- spsp is an spsp and a Carmichael number of the form: n = q(1)q(2)q(3) with each prime factor q(i) 3 mod 4.)
机译：令n> 1为奇数复合整数。用d个奇数写n-1 = 2（s）d。如果对于某些r = 0、1，...，s-1，b（d）= 1 mod n或b（2rd）= -1 mod n，那么我们说n是对b的强伪素数，或者spsp（b）的简称。将psi（t）定义为所有前t个素数基数中最小的强伪素数。如果我们知道psi t的确切值，对于整数n si（t），我们将拥有易于实现的确定性有效素数测试算法。感谢Pomerance等。和Jaeschke的psi（t）已知为1 <= t <=8。psi（9），...，psi（12）的推测值由我们在之前的论文中给出（数学比较72（ 2003），2085-2097; 74（2005），1009-1024）。本文的主要目的是给出13 <= t <= 19时psi'（t）的精确值;给出psi'（20）的下界：psi'（20）> 10（36）;并给出K2-和C-3- spsp <10（36）的原因和数值证据来支持以下猜想：对于任何t> = 12的psi（t）= psi'（t）si''（t） ，其中psi（t）（res。psi“（t））（i）是所有前t个素数基数中最小的K2-（result。C-3-）强伪素数。为此，我们描述了计算和将两种类型的spsp <10（36）枚举到前9个素数基数。在PC Pentium IV / 1.8GHz上，整个计算大约花费了4000个小时。（回想一下，K2- spsp是以下形式的spsp：n =具有p，q质数和​​q-1 = 2（p-1）的pq;并且C-3-spsp是spsp和形式的Carmichael数：n = q（1）q（2）q（3 ），每个素数因子q（i）3 mod4。）

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号