Numeros Aleatorios com Tamanho variavel / Inteiros Gigantes

28 de outubro de 2009 6 respostas

M

mcdruga 28 de outubro de 2009

Prezados,

Possuo dois problemas, os procurei na net e no forum mas não achei resposta. Peço desculpas caso esteja postando algo repetido.

1º - Devo manipular (fazer operações, mod, soma, divisão, exponenciação…) Numeros com 300 algarismos, e gostaria de saber que pacote devo utilizar, o que fazer!!!

2º - Preciso gerar números aleatórios que variam de 45 algarismos até 100 algarismos.
Pensei em usar algumas vezes o math.random, transformar os resultados em uma string e ir compondo, quando tivesse uma sting de tamanho X dava um cast para o tipo utilizado na pergunta 1.
No entanto nao sei se isso seria muito Inteligente.
Logo, gostaria de saber se alguem poderia propor uma forma de gerar e manipular esses números, e como seria o cast de uma String para esse tipo.

OBS: Alguem deve estar se perguntando pra que isso. Meu problema é: Compor um número de 200 algarismos seguindo vários critérios, e ““provar”” que esse número é primo, utilizando Miller-Rabin, sem utilizar os métodos que já estão prontos a milhares de anos… Tudo isso é fácil, o problema está nas operações de teste de MillerRabin que me pede operações como 23^X (Onde X é esse numero de 200 algarismos). Bom isso foi so para ilustrar.

Agradeço a ajuda

6 Respostas

E

entanglement 28 de out. de 2009

java.math.BigInteger
Essa classe tem um método chamado “probablePrime” que recebe 2 parâmetros: o tamanho do inteiro em bits (300 algarismos decimais = 997 bits - basta multiplicar 300 por log 10 / log 2), e um gerador de números aleatórios.

Se quiser, em vez de usar probablePrime, gerar seu próprio número aleatório, use java.util.Random, que pode gerar um byte array contendo bytes aleatórios, e passar esse byte array para criar um java.math.BigInteger. Por exemplo, se você quer gerar um número aleatório de 1024 bits, então aloque um array de 128 bytes, e peça para java.util.Random preencher esse array. Então você passa esse array para um dos construtores de java.math.BigInteger.

E

entanglement 28 de out. de 2009

23 elevado a um número de 200 algarismos resulta em um número de 10^200 * log 23 = 1,36 x 10^200 algarismos, algo que você não pode representar em nenhum computador existente ou que virá a existir, já que o número de elétrons no universo é de cerca de 10^80.

Portanto você vai ter de ver as contas corretas a serem feitas. Provavelmente você efetuará a exponenciação MODULO alguma coisa, ou seja, irá usar o método modPow de java.math.BigInteger.

E

entanglement 28 de out. de 2009

Miller-Rabin é um teste que indica se o número pode ser primo com grau muito grande de certeza. Mas para você ter certeza absoluta, você pode usar o algoritmo AKS:

E

entanglement 28 de out. de 2009

Olhando o fonte do JDK, probablePrime usa Miller-Rabin e Lucas-Lehmer, para dar o máximo de grau de certeza possível segundo ANSI X9-80.

M

mcdruga 28 de out. de 2009

Sim sim…
Eu não preciso calcular exatamente o valor de 23^ um numero de 200 algarismos…
Mas sim o Mod(23 ^elevado a esse numero).

No entanto preciso representar esse numero de 200 algarismos, e nao sei como fazê-lo…
Estou tentando utilizar o BigInteger e de fato gerar os numeros aleatorios e etc…

Obrigado pela ajuda…
Se possuir algum exemplo de código que utilize BigInteger, agradeço…

E

entanglement 28 de out. de 2009

import java.math.*;
class ModPow {
    public static void main(String[] args) {
        // Calcular 223 elevado a 1024, modulo 7.
        BigInteger bi = new BigInteger ("223");
        System.out.println (bi.modPow (new BigInteger ("1024"), new BigInteger ("7")));
    }
}

Criado 28 de outubro de 2009

Ultima resposta 28 de out. de 2009

Respostas 6

Participantes 2