I've been looking at simultaneous rational approximation with respect to modular arithmetic. One can 'factor' any number mod n into two numbers whose logs sum to log n easily using a continued fraction: Let m be the number we're trying to 'factor', and n be the modulus. We take cf(m/n) and find a convergent p/q. Multiply m by q, reduce mod n, and you get a number p' that is (lg m - lg q) bits long. Then m = p'/q mod n. For example, let n=629287. I want to 'factor' 529287. The continued fraction for 529287/629287 = [0 1 5 3 2 2 2 2 1 3 3 1 4 1 7]. The denominators of the convergents are 1,1,6,19,44,107,258,623,... Taking 258 as my denominator we expect that p' will be (6-3)=3 digits long. 529287*258 = 767 (Yep!), so one can "factor" 529287 as 767/258 mod 629287. What if we use bcf's for doing the approximation? Let k*m be the number we're trying to factor. Using bcf's, we take bcf (k/n, m/n) and find convergents p/r, q/r. Multiply k,m by r, reduce by n, and you get p',q' that are smaller than k,m. k, m = p'/r, q'/r mod n. Experimentally, lg p',q' ~= (lg k,m - .5 lg r), so we don't do any better than with simple continued fractions. Has anyone proven that one can't do better with any method of approximation? -- Mike Stay staym@datawest.net