Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #1 to TR23-200 | 19th December 2023 23:22

An Efficient Deterministic Primality Test


Revision #1
Authors: Joseph Shunia
Accepted on: 19th December 2023 23:22
Downloads: 174


A deterministic primality test with a polynomial time complexity of $\tilde{O}(\log^3(n))$ is presented. Central to our test is a novel polynomial reduction ring, applied to efficiently validate the polynomial congruence $(1 + x)^n \equiv 1 + x^n \pmod{n}$, a condition that holds exclusively for prime $n$. The test is grounded in our main theorem, supported by a series of lemmas, which collectively show how the congruence is verified through polynomial expansion within our reduction ring.

Changes to previous version:

Clarify test conditions. Revise main theorem and its proof. Add new supporting identities and lemmas. Update presentation.


TR23-200 | 6th December 2023 23:35

An Efficient Deterministic Primality Test

Authors: Joseph Shunia
Publication: 10th December 2023 07:18
Downloads: 625


A deterministic primality test with a polynomial time complexity of $\tilde{O}(\log^3(n))$ is presented. The test posits that an integer $n$ satisfying the conditions of the main theorem is prime. Combining elements of number theory and combinatorics, the proof operates on the basis of simultaneous modular congruences relating to binomial transforms of powers of two.


Comment #1 to TR23-200 | 18th December 2023 19:25


Authors: Pavel Pudlak
Accepted on: 18th December 2023 19:25


The argument with X,Y,Z (bottom of page 4 and top of 5) does not make much sense. I believe the proof is wrong.

Comment #2 to TR23-200 | 18th December 2023 22:05

RE: 1

Authors: Joseph Shunia
Accepted on: 18th December 2023 22:05


Pavel, thank you for reading my paper. I do agree that part of the proof is flawed. I was attempting to say that the sums are linearly independent modulo $n$, but in hindsight, my argument doesn't make much sense. I am working on revisions now and I will post them as soon as I can. Please share any other feedback or questions you have.

Comment #3 to TR23-200 | 21st December 2023 11:07

Status Update: Paper under review

Authors: Joseph Shunia
Accepted on: 21st December 2023 11:07


Dear eccc community,

Recent developments have brought to my attention the possibility of overlap with existing conjectures within the field. Additionally, there are concerns that some of the assumptions made in my proofs may not be robust enough to fully support the conclusions drawn. I am in the process of conducting a thorough review to understand the extent of these overlaps and their implications on the originality and validity of my work. This review is being undertaken with a commitment to maintaining the integrity and accuracy of the academic record.

Further details will be provided as soon as a more definitive assessment is available.

I appreciate your understanding and patience during this time.

Joseph M. Shunia

Comment #4 to TR23-200 | 23rd December 2023 21:45


Authors: Joseph Shunia
Accepted on: 23rd December 2023 21:45


I would like to provide an update to the ECCC community. Following my previous comment, I am undertaking a thorough re-evaluation of the paper.

This re-evaluation is focused on ensuring that all assumptions made in the paper are clearly stated and that any reliance on existing conjectures or non-standard premises is explicitly acknowledged and justified. I understand the critical importance of clarity and precision in outlining the assumptions, and the relationship of my work to established conjectures and theories in the field.

Should this process reveal that these concerns cannot be satisfactorily resolved, I am prepared to retract the paper.

I appreciate the community's patience and understanding as I navigate through this process, and I will provide further updates as they become available.

ISSN 1433-8092 | Imprint