T-sequence apparatus and method for general deterministic polynomial-time primality testing and composite factoring

• US 20020099746A1
• Filed: 04/27/2000
• Published: 07/25/2002
• Est. Priority Date: 07/26/1999
• Status: Abandoned Application

• Current Assignee: Shaul Backal
• Original Assignee: Shaul Backal
• Inventors: Tie, Teck Sing, Backal, Shaul O.
• Application Number:
  US09/559,142
• Publication Number:
  US 20020099746A1
• Time in Patent Office: Days
• US Class Current: 708/254
• CPC Class Codes: G06F 2207/7204 Prime number generation or prime number testing
• CPC Class Codes: G06F 7/586 using an integer algorithm, e.g. using linear congruential method
• CPC Class Codes: G06F 7/72 using residue arithmetic
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator
• CPC Class Codes: H04L 9/3033 details relating to pseudo-prime or prime number generation, e.g. primality test

Abstract

Using a new mathematical technique called the T-sequence, the inventor has discovered a powerful primality testing method that meets all four conditions above. A similar approach can be applied to perform fast factoring for numerous special cases, a method that can, in all liklihood, be extended to the general case, making possible a general and fast factoring algorithm. (Researchers heretofore have been able to factor only in sub-exponential time, never in polynomial time.) The same T-sequence can be used to construct a prime number formula (long sought after but never achieved) and a good random number generator. The former can be used to generate infinitely many prime numbers of any size efficiently, and the latter can generate non-periodic and absolutely chaotic random numbers. These aft numbers are widely used in all areas of industrial and scientific simulations. In general, the T-sequence can be used to handle efficiently the fundamental problems concerning prime numbers (which include primality testing, factoring, prime number formula, infinite-pattern prime problem, etc.).

Claims

1. A computer-implemented method, comprising:

determining at least one element of a non-montonic sequence, the non-montonic sequence being one of a family of related non-montonic sequences;

using at least said element, determining at least one property of a number; and

depending on said property, taking an action the effect of which is to enhance or degrade data security within a computer system or network.

2. The method of claim 1, wherein said property is primality.

3. The method of claim 1, wherein said number is a composite number, and said property is a factor of said number.

4. The method of claim 1, wherein said family of related non-montonic sequences is defined as follows:

5. A prime number generator, comprising:

means for generating candidate numbers by forming at least one of sums and differences of a given number and a series of prime numbers; and

means for deterministically evaluating primality of each of the candidate numbers in polynomial time.

6. The apparatus of claim 5, wherein said means for deterministically evaluating primality comprises means for determining at least one element of a non-montonic sequence, the non-montonic sequence being one of a family of related non-montonic sequences.

7. The apparatus of claim 6, wherein said family of related non-montonic sequences is defined as follows:

8. A random number generator, comprising:

means for determining a seed number;

means for forming at least one of sums and differences of the seed number and a series of prime numbers; and

means for outputting last digits of the series of prime numbers to produce a set of random digits.