Nombre premiers : demande confirmation

[Anonyme]

bonjour a tous
je ne suis qu'un beotien en math. comme je prend
le train tous les jours, je me suis pris au jeu
de la réflexion sur les nombres premiers.
voila ce que j'ai trouvé tout seul dans mon
train. Merci de me dire si c'est juste d'une
part et original d'autre part. peut-etre que
je viens de re-decouvrir le fil à couper le beurre
pour la 1000 eme fois!
Donc voici la chose exprimee avec mon vocabulaire
d'arithmétique elementaire:

Un nombre premier ne peut se terminer que par 1,3,7 ou 9.
on remarque une symetrie centrale: 1 - 9 et 3 - 7 autour
de 5.
Hors en poursuivant la reflexion sur les symetries, ces
quatre nombres ont les proprietes multiplicatives remarquables
suivantes exprimees sous forme d'un tableau 4x4

1 3 7 9

3 9 1 7

7 1 9 3

9 7 3 1

il s'agit du dernier chiffre de la multiplication d'un de
ces 4 nombres par l'un d'entre eux.
A nom avis ce tableau remarquable met en evidence les
propriétés suivantes:
Ces nombres restent entre eux avec l'operateur multiplier.
ce tableau possede une double symetrie sur ses deux diagonales.
chaque ligne ou chaque colonne ne comporte qu'une fois
chacun des 4 elements.

En reprenant le raisonnement à partir de ce tableau, est-ce
qu'on peu dire qu'un nombre quelconque se terminant
par 1, 3, 7 ou 9 est un candidat à etre premier. s'il n'est pas
premier il ne peut etre obtenu que par le produit de deux
nombres se terminant par un couple de chiffres pris
dans cet ensembles {1,3,7,9}.
Ce qui nous donne:
Pour 1 : que les couples 1-1, 3-7 et 9-9
Pour 3 : que les couples 1-3 et 7-9
Pour 7 : que les couples 1-7 et 3-9
Pour 9 : que les couples 1-9, 3-3 et 7-7

Compte tenu du raisonnement précédent, est-ce juste de dire
que si un nombre se termine par exemple par 3, pour savoir
s'il est premier il suffit de le diviser par tous
les nombres inférieurs à sa racine carrée se terminant
par 1 ou 7 d'une part ou par 3 ou 9 d'autre part. Hors la divisbilité
par 3 et 9 est obtenue immédiatement par la somme des
nombres qui composent ce chiffre qui doit etre un multiple
de 3 ou de 9.
Le but est de réduire le nombre de boucles de calcul de
l'algo de recherche d'un nombre premier.
Malheureusement, nombre de boucles de calcul reste encore exponentiel
au nombre de chiffres du nombre dont on recherche la primalité.

Voili,voila qu'en pensez-vous?
bien cordialement
jean-pierre cros

[Anonyme]

Bonjour,

jean-pierre cros a écrit :
....
>
> Compte tenu du raisonnement précédent, est-ce juste de dire
> que si un nombre se termine par exemple par 3, pour savoir
> s'il est premier il suffit de le diviser par tous
> les nombres inférieurs à sa racine carrée se terminant
> par 1 ou 7 d'une part ou par 3 ou 9 d'autre part. Hors la divisbilité
> par 3 et 9 est obtenue immédiatement par la somme des
> nombres qui composent ce chiffre qui doit etre un multiple
> de 3 ou de 9.

La divisibilité par un nombre *se terminant par* 3 n'a rien à voir
avec la divisibilité par 3.
143 = 11*13 divisible par un nombre se terminant par 3, et pourtant
pas divisible par 3 !

> Le but est de réduire le nombre de boucles de calcul de
> l'algo de recherche d'un nombre premier.

On réduirait encore plus si le nombre était écrit en base 6 au lieu de 10 :
seuls les nombres (>3) de la forme 6k +/- 1 peuvent être premiers soit 33 %
au lieu de 10k +/- 1 et 10k +/- 3 soit 40%

> Malheureusement, nombre de boucles de calcul reste encore exponentiel
> au nombre de chiffres du nombre dont on recherche la primalité

Non. Pas pour chercher si n est premier, pour trouver des diviseurs de n
ce qui n'est pas la même chose.

Il y a une large littérature (à lire donc) sur ce sujet.

Deux problèmes différents :
1) déterminer si un nombre est premier ou pas
(c'est à dire chercher des nombres premiers)
Ceci se fait par des algorithmes bien plus efficaces que chercher
des diviseurs (basés sur le petit théorème de Fermat et dérivés par
exemple)

2) trouver tous les diviseurs 1<d<n d'un nombre n
Certes si on n'en trouve pas, c'est que le nombre est premier, mais
c'est beaucoup plus long.

La base de la cryptographie à clé publique (RSA et autres) est
justement que le problème (1) est beaucoup plus "facile" que le problème (2)
Il est aisé de trouver des nombres premiers à 200 chiffres
(générer une clé privée pour décoder et la clé publique = le produit de deux
nombres premiers)
beaucoup plus difficile ("exponentiel") de trouver la factorisation d'un nombre
de 200 chiffres (casser la clé publique pour trouver la clé privée)

Amicalement.

--
philippe
mail : chephip+misc at free dot fr
replace misc by news otherwise message will go to trash

[Anonyme]

Merci, j'ai vu ou j'ai déraillé (normal j'ai fait ca dans le train :-)))
Amicalement