Scholarlink

<p>Primality testing is an especially useful topic for public-key cryptography. In this paper, a novel primality test algorithm based on Pell’s cubic will be introduced, and its necessary primality conditions will be proved using three integer sequences connected to operations applied in the projectivization of Pell’s cubic. The number of operations involved in the test grows linearly with respect to the bit length <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="9_2025_2839_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">\(\log _2(n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mo>log</mo> <mn>2</mn> </msub> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> of the input integer <i>n</i>. The algorithm is deterministic for integers less than <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="9_2025_2839_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="27" /> </InlineMediaObject> <EquationSource Format="TEX">\(2^{36}.\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mn>2</mn> <mn>36</mn> </msup> <mo>.</mo> </mrow> </math></EquationSource> </InlineEquation></p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Novel Performant Primality Test on a Pell’s Cubic

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年4月15日

查看全文
  • Luca Di Domenico,
  • Nadir Murru

摘要

Primality testing is an especially useful topic for public-key cryptography. In this paper, a novel primality test algorithm based on Pell’s cubic will be introduced, and its necessary primality conditions will be proved using three integer sequences connected to operations applied in the projectivization of Pell’s cubic. The number of operations involved in the test grows linearly with respect to the bit length \(\log _2(n)\) log 2 ( n ) of the input integer n. The algorithm is deterministic for integers less than \(2^{36}.\) 2 36 .