Ok,

I came across something a little over a year ago, and I need some help.

Can anyone tell me the how many known ways there are to determine what the factors are for any given integer?.

Not just how many but the actual values.

I stumbled upon a way to do so, and have not found any references to the method I am using  although I have researched it for over a year.

For reference, I am not some fool that claims things without verifiable proofs.
I am well versed in mathematics, and have made many observations that would have profound implications in industry and academia.
No I will not provide insight into the method by which I produce my results.
Thia has not been published as of yet and to release information now would be foolish.
I have spoken with a very well known person and have NDAs signed that has verified the method but I need to further refine the principles before publishing.

I hope that some of you out there may be able help.
This is a very simple concept that has eluded the greatest minds for over 1000 years.
Implications for internet and financial security are far reaching and currently sits as a 900 billion dollar annually.
I am currently studying programming to develop software and design a rig to win both of the remaining EFF awards.
I would have outsourced the programming but was afraid that the software engineers would screw me over.


Thanks

I mean, the basic algorithm is a prime sieve, because a number is either prime or the multiplicand of other prime factors. You start at two, keep dividing and once the number's not evenly divisible by two, you start with 3, then 5, then 7, then 11, then on up through ascending primes. Keep a lookup table of factorized results so if you get to any number you've already factored before, the result is known. This is deterministic, hard-P brute force factoring, and I'm sure there are libraries of lookup tables with prime factors to work from so you don't actually have to start from "2" every time the program gets run.

I only ever got up to the usual two years of calc with diffeq and linear algebra needed for my modest engineering needs, so never dove deeper into other factoring methods. Tag for interest.

For instance (as I think you alluded to), public key encryption relies on the difficulty of factoring the product of two large primes.  Nobody has found an easy way to do that from what I know.  Quantum computing promises to do it, but that remains to be seen.

Are you just looking for methods, or for fast methods?   I don't think the latter exists yet.

.

Thanks for the response.

Yes I was making a reference to RSA encryption.

Example is that the public key is product of two primes so it is composite

The bit is just how many digits the number is.
I can factorize a 10,000 bit integer in a day perhaps hours without the use of division.

A table as suggested above would be in Petabytes or Exabytes of data even after compression to achieve what I am doing.
Yes the Sieve of Erotosanese is a good fundamental framework for primes but brute force division is still unbelievably resource dependent.

I am aware that no one has made public a way to do this but I am wondering if I am missing anything in my research that I have not found.

It does not have to be efficient just able to achieve a result such as I has stated.
Being able to tell what the factors are of a given integer.

I have came across logarithmic formulas that would give some asymptotic limiting behaviors but that was about all I have seen.

Or like the totient functio F(n) such as the number of integers k in the range 1 = k = n for which the gcd(n, k) is equal to 1
Not to be confused with Phi F = 1.618033988749895 much like how p(x) has nothing to do with Pi p = 3.1415926535

I am confident that some advances are not in the public domain.  Aside from the history of NSA hoovering up number theory talent and publishing privately, see also the Invention Secrecy Act.

I don't have any suggestions for you.  But it's an interesting problem.   In fact, I consider publication of an efficient/elegant (non-brute-force) solution of it the Black Swan of Black Swans, given the staggering reliance -- finance, national security, etc. -- on crypto.  Epiphanies can't be scheduled, so it's just an idea away.  Could be you.  Math is a field with new conceptual abstractions all the time, and with the right one ...

In before the "never understood math" heat-death-of-the-universe/can't-be-done comments.

Thanks,

I will have to look into the  Invention Secrecy Act as it's the first I have heard of it. I was however told that what I was doing could not be patented as a "method" due to some court ruling that stated that if it could "theoretically" be done with pen and paper (regardless if it took the lifespan of the universe) it would not be protected.

The person I was in contact with in regards to partnership in the project suggested that money could be made by leveraging companies but I wasn't sure if that was even considered legal.

You might find the last thread of April interesting, re the general problem domain.

https://www.metzdowd.com/pipermail/cryptography/2021-April/thread.html

Believe me when I say that i know it sounds crazy, but it did happen.

When you mention the NSA snatching up number theorists....
I can say that something kinda weird happened on my computer back when I first began contacting university professors and project investors while researching early last year.

I had three folders that I saved my work in on the desktop. One day, one of the folders was empty but had another folder in it that contained a web link. The folder properties show that it was created 6 months earlier. The name of the folder was an address
2C253 Washington, DC 203503000

C Ring of the Pentagon
Human Resources and Organizational
Management Branch
HROM (ARH) Branch, USMC

This was the link they gave, but last year it was some guy that was running it.
https://www.hqmc.marines.mil/hrom/Unit-Home/HROMNSFArlingtonOffice/

I had never even heard of this before and had to look up how the office numbering structure was at the Pentagon.


Basically it was a "how to" for recruitment of civilians and project funding,
Once you went through the process of logging into the private government network it stated that "this is purely voluntary" and "you are applying of your own free will"

Yeah.... it happened.  No, I did not pursue it further.

I did however start to keep my notes on paper.

Sounds like Cicada 3301 antics.

Up

I heard about that.
Didn't it turn out to be just some group of net neutrality hackers?

And you only have to bother searching up to SRT(N).

You should also be aware that actual high grade encryption algorithms do NOT rely on prime numbers.

Just very very large sequences that appear random.

I quit replying after the misappelation to SofE. I had nothing to add but folk wisdom after that, I guess.

Yes, it's tons more complicated than simple sieves.

ETA speeling

Are you referring to D-H and the order of G?
It is possible to solve that "Index"

Again I am assuming that you are referring to solving the decrete logarithmic problem which does rely on primes and the use of factorization.
A B keys can be random all they want but it assumes that a large enough P cannot be broken.

As for SofN graphically the boundary can be seen.
But it can only be looked at as a limit. a
Adding restrictions to that limit is where people miss out.

LFSR many millions of bits long.
Many with active tap changes.

Especially when you consider that all it takes is one key theorem to start a new field, which could yield minor or major advancement. It seems pretty easy to think that over 75 years of work there would be some sort of progression, or even MINOR progression in number theory. Just as an example, from what I recall game theory comes into existence from a re-imagining of one simple problem to a more broad abstract concept. The NSA are just hiring mathematicians for known public work? I doubt it, they clearly have some sub field of theory they are specialized in which isn't public.. Besides the fact that the NSA seems to publically be most interested in side-channel attacks and planting backdoors, which has always felt like a ruse to me to get people away from the actual mathematical work going on.

I have three patents, now expired, that are still under secrecy act coverage.
They deal with techniques for synchronizing oscillators to very precise alignment.

I received letters extending the protection out to 50 years.

I believe the expiration of the patents attracted a review and the determination to further extend the secrecy orders.

All they would tell me was that "there does not appear to have been a lot of progress in this area."

You don't say....

I find it very odd how you put it. "synchronizing oscillators to very precise alignment"
Of what order of magnitude were you able to achieve results?
Would you please describe the limiting behavior of your function..
I have also done what you are describing and made advancements to better than loglinear time.
Less than O(n log n) = O(log n!)

Your post makes me wonder if this was just a very clever idea that you had in regards to the subject or taken from someone else's work because I have seen many attempts of those that try to attribute harmonic oscillation to this behavior.
FFT is usually the best that they can do.

I have looked into the field of signals analysis for decomposition of wave forms and wave packets.
Very "interesting" stuff. Especially when you can isolate the carrier wave.
And then there are the implications that deal with particle wave physics.

Periodic oscillation patterns can be looked at as a fundamental byproduct of sequencing.


I am VERY intrigued as to your response  @brickeyee

A part in 1e-17.

It allows TDOA measurements to be very precise in locating a signal source.

It is bumping the Cramér–Rao bound and is well past the thermal noise bound.

Factoring is a lot slower than simply multiplying large primes until you find the correct pair to match the public key.

It's not slow at all if you know how to do it.

As for the method you describe.  "multiplying large primes"
I would say that your statement is true but unrealistic. No one can experimentally test this because the data storage requirements are too large.
Not to mention that the run time to isolate all the primes up to the given N.
The Prime Number Theorem: p(x) ~ x/ln x
The last one I know about was given for p(10^24) and was found by analytic continuation methods assuming the Riemann Hypothesis is true by J. Buethe, J. Franke, A. Jost, T. Kleinjung.
1,000,000,000,000,000,000,000,000 has
18,435,599,767,349,200,867,866  primes

That is only 24bit



Digits in a number and the amount possible answers.
Say we are talking about a 5,000 bit number.
Including zero, 2bit is 10 numbers 3bit is 100..and so on.
10×10×10×10×10...(N)bits-2 times or 4,998 times.
hyper-4 or tetration an operation that uses a iterated, or repeated, exponentiation to achieve the result as well.


PNT and even taking into account the limiting nature of 70 million described by Yitang Zhang you can see why what you say would not work.
The total number of combinations of 2 primes that would need to be multiplied together at random to get to the desired outcome is ridiculous.
Dividing the key by each of those primes allows the inverse to be known and would require much less work and time.
And that's IF you some how had the database of all primes p(x) for a number.
I've calculated this into harddrive space once. Even compressed it is in the exobytes of data.
1 exabyte (EB) = 1 million terabytes
And that's just to store the primes.


Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It narrows a lot of this down.

So I ask how do you determine what primes to multiply?
How do you even identify these primes?
How would you store the data?

For the most part everyone knows what the large primes used for public key generation.

Have computer time, start searching.


ETA:

A lot of how to attack problems like this depends on what resources you have available.

NSA has plenty of 'old' cray computers.
They are set up to do array calculations.
So if you can make the calculation look like a lot of array multiplications they are still VERY fast.


There are also HUGE arrays of 'engineering workstations.'
For the most part we used to joke about having "pizza box" farms.
No monitors.
Silicon Graphics was the hottest workstation computer back then.

It takes a decent crew to monitor the functioning of all the CPUs from a central control room.

There was also some specialized units for particular problems.

The development of multi-port memory chips drove performance to new levels.

No more having to pause calculations to read results from memory.
A separate CPU could read memory contents while calculations continued on another CPU.

I am not sure how this is interesting? What am I missing?

Most of the work I am aware of (I was a Crypto Mathematician at NSA), is how to do it faster. I never heard anyone ask how many ways could it be done?

The pizza box farms in old hanger style buildings are something to see.

Simply huge numbers of processors interconnected in some "interesting" ways.

"For  example,  to increase  by  two  orders  of  magnitude  the  size  of  a  problem
whose  sequential  performance  is  given  by t=c*n^4
requires,  optimistically, 100,000,000 processors"

Not out of reach given an adequate budget.
and 1 MByte of RAM in a processor is now well withing reach.