Starting from an index mapping for one to multi-dimensions, a general in-placeand in-order prime factor FFT algorithm is proposed in this paper. In comparing with existingprime factor FFT algorithms, this algorithm sa...Starting from an index mapping for one to multi-dimensions, a general in-placeand in-order prime factor FFT algorithm is proposed in this paper. In comparing with existingprime factor FFT algorithms, this algorithm saves about half of the required storage capacityand possesses a higher efficiency. In addition, this algorithm can easily implement the DFT andIDFT in a single subroutine,展开更多
Hashing and Trie tree data structures are among the preeminent data mining techniques considered for the ideal search. Hashing techniques have the amortized time complexity of O(1). Although in worst case, searching a...Hashing and Trie tree data structures are among the preeminent data mining techniques considered for the ideal search. Hashing techniques have the amortized time complexity of O(1). Although in worst case, searching a hash table can take as much as θ(n) time [1]. On the other hand, Trie tree data structure is also well renowned data structure. The ideal lookup time for searching a string of length m in database of n strings using Trie data structure is O(m) [2]. In the present study, we have proposed a novel Prime Box parallel search algorithm for searching a string of length m in a dictionary of dynamically increasing size, with a worst case search time complexity of O(log2m). We have exploited parallel techniques over this novel algorithm to achieve this search time complexity. Also this prime Box search is independent of the total words present in the dictionary, which makes it more suitable for dynamic dictionaries with increasing size.展开更多
The article is devoted to actual problems of prime numbers. A theorem that allows generating a sequence of prime numbers is proposed. An algorithm for generating prime numbers has been developed. A comparison of the p...The article is devoted to actual problems of prime numbers. A theorem that allows generating a sequence of prime numbers is proposed. An algorithm for generating prime numbers has been developed. A comparison of the proposed theorem, with Wilson’s theorem is also provided.展开更多
This paper proposes three new attacks. In the first attack we consider the class of the public exponents satisfying an equation e X-N Y ＋（ap^r＋ bq^r）Y = Z for suitably small positive integers a, b. Applying contin...This paper proposes three new attacks. In the first attack we consider the class of the public exponents satisfying an equation e X-N Y ＋（ap^r＋ bq^r）Y = Z for suitably small positive integers a, b. Applying continued fractions we show thatY/Xcan be recovered among the convergents of the continued fraction expansion of e/N. Moreover, we show that the number of such exponents is at least N^（2/（r＋1）-ε）where ε≥ 0 is arbitrarily small for large N. The second and third attacks works upon k RSA public keys（N_i, e_i） when there exist k relations of the form e_ix-N_iy_i ＋（ap_i^r ＋ bq_i^r ）y_i = z_i or of the form e_ix_i-N_iy ＋（ap_i^r ＋ bq_i^r ）y = z_i and the parameters x, x_i, y, y_i, z_i are suitably small in terms of the prime factors of the moduli. We apply the LLL algorithm, and show that our strategy enables us to simultaneously factor k prime power RSA moduli.展开更多
By extending both arithmetical operations into finite sets of natural numbers, from the entire set of natural numbers successively deleting some residue classes modulo a prime, we invented a recursive sieve method or ...By extending both arithmetical operations into finite sets of natural numbers, from the entire set of natural numbers successively deleting some residue classes modulo a prime, we invented a recursive sieve method or algorithm on natural numbers and their sets. The algorithm mechanically yields a sequence of sets, which converges to the set of all primes p such that 2p + 1 divides the Mersenne number Mp. The cardinal sequence corresponding to the sequence of sets is strictly increasing. So that we have captured enough usable structures, without any estimation, the existing theories of those structures allow us to prove an exact result: there are infinitely many Mersenne composite numbers with prime exponents Mp.展开更多
Cornachia’s algorithm can be adapted to the case of the equation x2+dy2=nand even to the case of ax2+bxy+cy2=n. For the sake of completeness, we have given modalities without proofs (the proof in the case of the equa...Cornachia’s algorithm can be adapted to the case of the equation x2+dy2=nand even to the case of ax2+bxy+cy2=n. For the sake of completeness, we have given modalities without proofs (the proof in the case of the equation x2+y2=n). Starting from a quadratic form with two variables f(x,y)=ax2+bxy+cy2and n an integer. We have shown that a primitive positive solution (u,v)of the equation f(x,y)=nis admissible if it is obtained in the following way: we take α modulo n such that f(α,1)≡0modn, u is the first of the remainders of Euclid’s algorithm associated with n and α that is less than 4cn/| D |) (possibly α itself) and the equation f(x,y)=n. has an integer solution u in y. At the end of our work, it also appears that the Cornacchia algorithm is good for the form n=ax2+bxy+cy2if all the primitive positive integer solutions of the equation f(x,y)=nare admissible, i.e. computable by the algorithmic process.展开更多
In this paper is demonstrated a method for reduction of integer factorization problem to an analysis of a sequence of modular elliptic equations. As a result, the paper provides a non-deterministic algorithm that comp...In this paper is demonstrated a method for reduction of integer factorization problem to an analysis of a sequence of modular elliptic equations. As a result, the paper provides a non-deterministic algorithm that computes a factor of a semi-prime integer n=pq, where prime factors p and q are unknown. The proposed algorithm is based on counting points on a sequence of at least four elliptic curves y2=x(x2+b2)(modn) , where b is a control parameter. Although in the worst case, for some n the number of required values of parameter b that must be considered (the number of basic steps of the algorithm) substantially exceeds four, hundreds of computer experiments indicate that the average number of the basic steps does not exceed six. These experiments also confirm all important facts discussed in this paper.展开更多
This work is devoted to the theory of prime numbers. Firstly it introduced the concept of matrix primes, which can help to generate a sequence of prime numbers. Then it proposed a number of theorems, which together wi...This work is devoted to the theory of prime numbers. Firstly it introduced the concept of matrix primes, which can help to generate a sequence of prime numbers. Then it proposed a number of theorems, which together with theorem of Dirichlet, Siegel and Euler allow to prove the infinity of twin primes.展开更多
A best algorithm generated scheme is proposed in the paper by making use of the thought of evolutionary algorithm, which can generate dynamically the best algorithm of generating primes in RSA cryptography under diffe...A best algorithm generated scheme is proposed in the paper by making use of the thought of evolutionary algorithm, which can generate dynamically the best algorithm of generating primes in RSA cryptography under different conditions. Taking into account the factors of time, space and security integrated, this scheme possessed strong practicability. The paper also proposed a model of multi-degree parallel evolutionary algorithm to evaluate synthetically the efficiency and security of the public key cryptography. The model contributes to designing public key cryptography system too.展开更多
The definition of Collatz Operator, the mathematical avatar of the Collatz Algorithm, permits the transformation of the Collatz conjecture, which is delineated over the whole natural number set, into an equivalent inf...The definition of Collatz Operator, the mathematical avatar of the Collatz Algorithm, permits the transformation of the Collatz conjecture, which is delineated over the whole natural number set, into an equivalent inference restricted to the odd prime number set only. Based on this redefinition, one can describe an empirical-heuristic proof of the Collatz conjecture.展开更多
基金Supported by the National Natural Science Foundation of China
文摘Starting from an index mapping for one to multi-dimensions, a general in-placeand in-order prime factor FFT algorithm is proposed in this paper. In comparing with existingprime factor FFT algorithms, this algorithm saves about half of the required storage capacityand possesses a higher efficiency. In addition, this algorithm can easily implement the DFT andIDFT in a single subroutine,
文摘Hashing and Trie tree data structures are among the preeminent data mining techniques considered for the ideal search. Hashing techniques have the amortized time complexity of O(1). Although in worst case, searching a hash table can take as much as θ(n) time [1]. On the other hand, Trie tree data structure is also well renowned data structure. The ideal lookup time for searching a string of length m in database of n strings using Trie data structure is O(m) [2]. In the present study, we have proposed a novel Prime Box parallel search algorithm for searching a string of length m in a dictionary of dynamically increasing size, with a worst case search time complexity of O(log2m). We have exploited parallel techniques over this novel algorithm to achieve this search time complexity. Also this prime Box search is independent of the total words present in the dictionary, which makes it more suitable for dynamic dictionaries with increasing size.
文摘The article is devoted to actual problems of prime numbers. A theorem that allows generating a sequence of prime numbers is proposed. An algorithm for generating prime numbers has been developed. A comparison of the proposed theorem, with Wilson’s theorem is also provided.
文摘This paper proposes three new attacks. In the first attack we consider the class of the public exponents satisfying an equation e X-N Y ＋（ap^r＋ bq^r）Y = Z for suitably small positive integers a, b. Applying continued fractions we show thatY/Xcan be recovered among the convergents of the continued fraction expansion of e/N. Moreover, we show that the number of such exponents is at least N^（2/（r＋1）-ε）where ε≥ 0 is arbitrarily small for large N. The second and third attacks works upon k RSA public keys（N_i, e_i） when there exist k relations of the form e_ix-N_iy_i ＋（ap_i^r ＋ bq_i^r ）y_i = z_i or of the form e_ix_i-N_iy ＋（ap_i^r ＋ bq_i^r ）y = z_i and the parameters x, x_i, y, y_i, z_i are suitably small in terms of the prime factors of the moduli. We apply the LLL algorithm, and show that our strategy enables us to simultaneously factor k prime power RSA moduli.
文摘By extending both arithmetical operations into finite sets of natural numbers, from the entire set of natural numbers successively deleting some residue classes modulo a prime, we invented a recursive sieve method or algorithm on natural numbers and their sets. The algorithm mechanically yields a sequence of sets, which converges to the set of all primes p such that 2p + 1 divides the Mersenne number Mp. The cardinal sequence corresponding to the sequence of sets is strictly increasing. So that we have captured enough usable structures, without any estimation, the existing theories of those structures allow us to prove an exact result: there are infinitely many Mersenne composite numbers with prime exponents Mp.
文摘Cornachia’s algorithm can be adapted to the case of the equation x2+dy2=nand even to the case of ax2+bxy+cy2=n. For the sake of completeness, we have given modalities without proofs (the proof in the case of the equation x2+y2=n). Starting from a quadratic form with two variables f(x,y)=ax2+bxy+cy2and n an integer. We have shown that a primitive positive solution (u,v)of the equation f(x,y)=nis admissible if it is obtained in the following way: we take α modulo n such that f(α,1)≡0modn, u is the first of the remainders of Euclid’s algorithm associated with n and α that is less than 4cn/| D |) (possibly α itself) and the equation f(x,y)=n. has an integer solution u in y. At the end of our work, it also appears that the Cornacchia algorithm is good for the form n=ax2+bxy+cy2if all the primitive positive integer solutions of the equation f(x,y)=nare admissible, i.e. computable by the algorithmic process.
文摘In this paper is demonstrated a method for reduction of integer factorization problem to an analysis of a sequence of modular elliptic equations. As a result, the paper provides a non-deterministic algorithm that computes a factor of a semi-prime integer n=pq, where prime factors p and q are unknown. The proposed algorithm is based on counting points on a sequence of at least four elliptic curves y2=x(x2+b2)(modn) , where b is a control parameter. Although in the worst case, for some n the number of required values of parameter b that must be considered (the number of basic steps of the algorithm) substantially exceeds four, hundreds of computer experiments indicate that the average number of the basic steps does not exceed six. These experiments also confirm all important facts discussed in this paper.
文摘This work is devoted to the theory of prime numbers. Firstly it introduced the concept of matrix primes, which can help to generate a sequence of prime numbers. Then it proposed a number of theorems, which together with theorem of Dirichlet, Siegel and Euler allow to prove the infinity of twin primes.
基金Supported by the Hi-Tech Research and Development Program of China(2002AA1Z1490)
文摘A best algorithm generated scheme is proposed in the paper by making use of the thought of evolutionary algorithm, which can generate dynamically the best algorithm of generating primes in RSA cryptography under different conditions. Taking into account the factors of time, space and security integrated, this scheme possessed strong practicability. The paper also proposed a model of multi-degree parallel evolutionary algorithm to evaluate synthetically the efficiency and security of the public key cryptography. The model contributes to designing public key cryptography system too.
文摘The definition of Collatz Operator, the mathematical avatar of the Collatz Algorithm, permits the transformation of the Collatz conjecture, which is delineated over the whole natural number set, into an equivalent inference restricted to the odd prime number set only. Based on this redefinition, one can describe an empirical-heuristic proof of the Collatz conjecture.
