Die Mathe-Redaktion - 19.12.2014 19:11 - Registrieren/Login
Auswahl
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Oktober 2014

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 289 Gäste und 34 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Wauzi
Mathematik » Zahlentheorie » Primitivwurzel
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Primitivwurzel
rijndael
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.12.2007
Mitteilungen: 19
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2008-02-13 09:45


Hi Leutz,

gibt es ein Kriterium dafür, ob eine Zahl n Primitivwurzel bzgl. einer gegebenen Primzahl p ist. Der einfachste Weg wäre die BruteForce-Methode:
Java
for(int i=0;i<p;i++){
  if(powmod(n,i,p)==0) return false;
}
Diese hat aber sehr lange Laufzeit. Gibt es ein "schnelleres" Kriterium?

thx
rijn



  Profil  Quote  Link auf diesen Beitrag Link
dettman
Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 26.11.2003
Mitteilungen: 557
Aus: nähe Frankfurt
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2008-02-13 09:51


Hi!

Soweit ich weiß ist das Finden der Primitivwurzeln sehr schwierig und geht nur durch probieren. Aber man kann die Anzahl der Primitivwurzel bestimmen und sogar die anderen Primitivwurzeln easy finden, wenn man eine hat.

fed-Code einblenden

Viele grüße
dettman

[ Nachricht wurde editiert von dettman am 13.02.2008 09:58:32 ]



  Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Kay_S
Senior Letzter Besuch: im letzten Monat
Dabei seit: 06.03.2007
Mitteilungen: 1208
Aus: Vallendar bei Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2008-02-13 11:23


Hi,

fed-Code einblenden

Kay
[ Nachricht wurde editiert von Kay_S am 13.02.2008 11:25:59 ]



  Profil  www  Quote  Link auf diesen Beitrag Link
owk
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 10.01.2007
Mitteilungen: 6957
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2008-02-13 11:38


Man kann noch weiter auf die maximalen Teiler von φ(p) einschränken, d.h. diejenigen Teiler d, für die φ(p)/d prim ist (vgl. Wikipedia). owk



  Profil  Quote  Link auf diesen Beitrag Link
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 39199
Aus: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2008-02-13 11:53


2008-02-13 11:23 - Kay_S schreibt:
... Faktorisierung von p-1, wofür kein polynomieller Algorithmus bekannt ist (es geht aber subexponentiell).
Hi Kay,
von den Quantencomputern von Shor abgesehen, hat sich dies doch, soweit ich gelesen habe, vor kurzem geändert, siehe hier.
In den Kommentaren, die ich dazu an verschiedenen Stellen fand, wird das als einer der größten Durchbrüche in der Algorithmentheorie ("Prime factorization is in P") gefeiert.
Ich finde aber diese Kommentare nicht so schnell wieder.

Ich weiß, daß man mit dem Begriff "Polynomialzeit-Algorithmus" vorsichtig umgehen muß, vor allem, was die Berücksichtigung der Eingabelänge betrifft. Sorry, wenn ich irgendetwas falsch verstanden habe.
Gruß Buri


-----------------
Cette question nous entraînerait trop loin. (Diese Frage würde uns zu weit führen) Henri Poincaré (1854-1912)



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: im letzten Monat
Dabei seit: 06.03.2007
Mitteilungen: 1208
Aus: Vallendar bei Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2008-02-13 12:06


Hi Buri,

Da geht es ganz eindeutig um "Primality Proving", was seit 2002 als effizient lösbar bewiesen wurde.

Beim Faktorisieren muss man nicht nur entscheiden, ob eine zusammengesetzte Zahl vorliegt, sondern auch noch die Faktoren liefern. Ich glaube nicht, dass jemand da einen Polynomialzeitalgorithmus gefunden hat. Das wäre ja ein "Skandal", da sofort RSA & Homebanking unsicher wären.

Kay



  Profil  www  Quote  Link auf diesen Beitrag Link
Bewerte diesen Thread:
[Was sonst bewertet wurde]
 Neues Thema [Neues Thema]

 Antworten [Antworten]   

 Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2014 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]