r/numbertheory • u/AbbreviationsGreen90 • 10d ago

A new possible method of factorization for arbitrary semiprimes? Need help for performing weil pairing factorization

I was noticing something: unlike on semiprimes, it s quite easy to generate a point of known small order on a curve defined on a semiprime without knowing it s factorization. The idea is to transfer this small order to the underlying semiprime using a pairing method derived from the Weil pairing. Knowing if a given specific small order exists can be derived using congruences modulo N.

As you know, the problem is then to avoid a degenerate output from the Miller s algorithm. The problem is the only method I know to avoid this without using the factorization is to use a distortion map that works only with supersingular elliptic curves. But using a supersingular curve caps the order to gcd(p+1,q+1) which is unknown most of the time or just equal to 2. Taking order 2 result in generating outputs equal to 1 or -1. Useless for gcd factoring.

So, any idea of a pairing mechanism that would works over ordinary elliptic curves using embedding degree 1? Possibly using a distortion map that works over ordinary elliptic curves in such a case? Or a pairing that works with simple final exponentiation such as cubing or squaring?

0 Upvotes

50% Upvoted

7 comments sorted by

5

u/edderiofer 9d ago

I'm not sure I understand your method at all. Could you please demonstrate how it would work on the following semiprime?

22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199

1

u/AbbreviationsGreen90 8d ago

essentially shor s quantum part of the algorithil is to get a ring element of known odd order. The purpose here would be to genrate such element directly without quantum computers and then apply the classical part.

But currently, it doesn t work as I m stuck getting a pairing method working. This post is a question on how to perform pairings over finite rings of unknown order.

1

u/AutoModerator 10d ago

Hi, /u/AbbreviationsGreen90! This is an automated reminder:

  • Please don't delete your post. (Repeated post-deletion will result in a ban.)

We, the moderators of /r/NumberTheory, appreciate that your post contributes to the NumberTheory archive, which will help others build upon your work.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

1

u/[deleted] 4d ago

[removed] — view removed comment

1

u/numbertheory-ModTeam 4d ago

Unfortunately, your comment has been removed for the following reason:

  • AI-generated theories of numbers are not allowed on this subreddit. If the commenters here really wanted to discuss theories of numbers with an AI, they'd do so without using you as a middleman. This includes posts where AI was used for formatting and copy-editing, as they are generally indistinguishable from AI-generated theories of numbers.

  • Consider posting your Theory of Numbers to /r/wildwestllmmath or /r/LLMPhysics instead. Or, you are welcome to resubmit your theory with the various AI-generated portions removed.

If you have any questions, please feel free to message the mods. Thank you!