검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Inefficacious Conditions of the Frobenius Primality Test and Grantham's Problem Frobenius 원시성 검정의 비효율적인 조건과 Grantham 문제

Naoyuki SHINOHARA

  • 조회수

    0

  • 이것을 인용

요약 :

입력 숫자가 소수인지 여부를 결정하는 데에는 두 가지 종류의 알고리즘이 있습니다. 소수성 테스트소수 증명. 에이 소수성 테스트 매우 효율적이지만 확률적입니다. 즉, 소수를 결정하는 데 특정 오류가 있습니다. 반면에, 소수 증명 항상 정답을 제시하지만 그다지 효율적이지는 않습니다. Grantham은 Quadratic Frobenius Test에서 매우 흥미로운 문제를 제안했습니다.QFT) 이는 소수성 테스트. 문제를 부정적으로 해결하면 다음과 같은 결과를 얻을 수 있습니다. 소수 증명 기존의 어떤 것보다 효율적이다. 소수 증명. Grantham의 문제를 해결하려면 언제 연구해야 하는지가 중요합니다. QFT 실패합니다. 본 논문에서는 Grantham 문제를 해결하기 위한 첫 번째 단계로 주어진 홀수 합성수에 대한 두 가지 조건을 제시합니다. n 및 매개 변수 a,b of QFT 그렇게 n 패스 QFT for a,b. 이러한 조건을 바탕으로 우리는 문제가 부정적으로 해결될 것이라고 제안할 수 있는 계산 실험을 수행했습니다. 더욱이, 두 조건은 쌍을 계산하는 두 가지 알고리즘을 제공합니다(a,b) 주어진 홀수 합성수에 대해 n 패스 QFT어디로 n의 소인수분해가 알려져 있습니다.

발행
IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.11 pp.3325-3334
발행일
2008/11/01
공개일
온라인 ISSN
1745-1337
DOI
10.1093/ietfec/e91-a.11.3325
원고의 종류
PAPER
범주
암호화 및 정보 보안

작성자

키워드