ИСТИНА |
Войти в систему Регистрация |
|
ИСТИНА ЦЭМИ РАН |
||
We consider applications of the modular arithmetic to cumbersome compu- tational tasks, i.e. to problems with a lot of operations with cumbersome numbers. Such problems often arise in computer algebra tasks. We mean evaluations of long polynomials with huge numerical coeffcients. Traditionally a modular arithmetic is used for each separate arithmetic operation. But It is more effective to execute the programs from the beginning till the end modulo one prime. After several such calculations in modulo different primes we can finally restore the right values of all numbers of the result. With respect of the Chinese remainder theorem if you know remainders from division of a natural number by a number of noncompa- rable natural numbers you can restore the original number itself if it is not more than multiplication of all these divisors. We assume that all numbers in the problem are integer or rational. There is an generalization of the Chinese theorem for integer and rational numbers.