Algebraic Number Reconstruction And Application

Rational number reconstruction can be divided into two cases, for the first case, it can be described as follows: Given a modules M and a residue U∈Z/(M) , how to get a rational number R = A/B for which the congruence R≡U (mod M) is satisfied. The second case, given a float number r who can approximate to m/ n at any accuracy, how can we get m/ n exactly?In this paper, we conclude the ideal and algorithm for rational number reconstruction and algebraic number reconstruction. For the rational reconstruction, the problem we discussed is as follows: suppose we want to compute a rational m/ n, we only know an upper bound N of denominator of this number, and an numerical method to compute an approximate of this rational number at any accuracy, but can not reach the exact number. How can we compute the rational number from one of these approximations and upper bound N ? To solve this problem, first, we must how approximate of the approximation attached that can insure us to get the rational number exactly, and then give a algorithm for rational reconstruction.According to the ideal given by Zhang Jingzhong and his companies, they obtain rational number from its approximation by fraction method. Here, we give the definition of continued fraction first:Definition 0.1 Suppose a0 , a1 , are real number sequence, and a j>0 for any j≥1. For any given number N >0, we call the expression as (N -order) finite continued fraction.Theorem 0.1 Let be a reduced proper fraction (which m andn are co-prime), and N≥max{n ,2}.Assume that there is a float number w suehthat If we get Positive rational numbersueh that andq'N,then it holds thatTheorem 0.1 tells us a faet that:if we want to reeover a rationalnumber but we only know the uPPer bound N of denominator of thisnumber and a aPProximate number w that satisfythere 15 a unique rational number whose denominator 15 less than N inthe range But, not all the approximation w and rational number that satisfy the condition of therom0.1 can we recover the rational number by its approximation.Theorem 0.2 Let be a reduced proper fraction and r its approximation. Suppose m, n are positive numbers, and N≥max{n ,2}. Let K be a random positive integer, the continued fraction expressions of m /n and r are [ a0 , a1 , , a N] and [b 0 , b1 , , bM ] respectively. Let d = r ? m / n < 1/((2 K + 2) N ( N? 1)), then one of the follows results holds: 1. ai = bi , i = 0,1,..., N ;bN +1≥K. 2. ai = bi , i = 0,1,..., N ? 1; bN = a N ? 1, bN +1 = 1,bN +2≥KFrom therom0.2, we can use algorithm 3.1 to recover the rational number exactly.For the algebraic number reconstruction, the problem is described as follows: Suppose we have known a float numberαwhich is an approximation of unknown algebraic number, and also we knew the degree and the height ofα, how to obtainαexactly by the given condition? In fact, algebraic number reconstruction is equivalent to recover the minimal polynomial of it. Here, we mainly use the PSQL algorithm. Let v = (1 ,α,,αn), we have following result: Theorem 0.3 Letε=α?αwhich satisfiesLet G ( x) is the result of using PSQL algorithm on v , then the primitive part of G (x) is the minimal polynomial ofα.Algorithm3.5 gives the algorithm for recover an unknown algebraic number by its approximation.In the end of this paper, examples about polynomial factorization and find the real roots of polynomial are given for the application of rational number and algebraic number reconstruction.