QED

In het septembernummer van PC-Active gaat mijn Denkwerk-rubriek over het factoriseren van grote getallen. Aanleiding was de factorisatie van 21039 - 1 eind mei. Daar begint het artikel dan ook, maar ik bespreek ook vorige records, vooral van de RSA Factoring Challenge. Ik leg ook in grote lijnen de werking van de Rational Sieve uit [...]

Randall Munroe scoort weer:

Onderzoeker Richard Crandall verkoopt via zijn bedrijf Perfectly Scientific posters van de grootst bekende priemgetallen. De posters meten 74 bij 102 cm en bevatten alle cijfers van een Mersennepriemgetal. Zijn nieuwste poster bevat het huidige grootst bekende priemgetal: 232582657 - 1, een getal van 9 808 358 cijfers. Daarvoor tel je wel 100 dollar neer, [...]

Een nieuw record: onderzoekers van Nippon Telegraph and Telephone Corporation hebben in samenwerking met de universiteit van Bonn en de Ecole Polytechnique Fédérale te Lausanne (EFPL) voor het eerst een getal van meer dan 1000 bits gefactoriseerd. Ze gebruikten hiervoor de Special Number Field Sieve. Het vorige record met dit factorisatiealgoritme bedroeg 911 bits. Het [...]

In het meinummer van PC-Active heb ik een artikel over kwantumcomputers geschreven. De aanleiding was het nieuws in februari dat het Canadese bedrijf D-Wave de eerste commerciële kwantumcomputer zou gebouwd hebben. Ik vond dit een mooie gelegenheid om eerst eens te kijken naar fundamentelere zaken: wat is een kwantumcomputer en hoe werkt die?

In het [...]

In het aprilnummer van PC-Active staat een artikel van mij over DNA-computers en probabilistische priemtesten. Wat beide onderwerpen met elkaar gemeen hebben is dat het voorbeelden zijn van wiskundige bewijsmethodes die geen zekerheid bieden, maar wel met een hele grote waarschijnlijkheid een oplossing geven. Ik bespreek er de Miller-Rabin test om te bepalen of een [...]

Vandaag is het π-dag. In de Amerikaanse notatie wordt 14 maart namelijk geschreven als 3/14. Voor de wiskundemeisjes was dat vorig jaar de gelegenheid om met hun blog te beginnen. Voor mij is dat vandaag de gelegenheid om enkele π-weetjes te schrijven.
Toen Ferdinand von Lindemann eens een lezing gaf over zijn bewijs dat π een [...]

Lezer Pim van Tend liet me onlangs weten dat hij op zijn website een computerprogramma heeft gezet dat automatisch Kakuro-puzzels kan oplossen. Een Kakuro is een soort kruiswoordraadsel, maar dan met cijfers in plaats van letters. Op Kakuro.com wordt Kakuro beschreven als “Sudoku’s bigger (and harder) brother”. In het Nederlands wordt het ook wel eens [...]

Shors algoritme is het bekendste voorbeeld van een algoritme voor een kwantumcomputer. Het laat toe om getallen te factoriseren, en dat veel efficiënter dan op een klassieke computer kan. Net zoals bij de vierkleurenstelling gebeurt, overschaduwt dit algoritme alle andere kwantumalgoritmes. Vaak wordt Shors algoritme ten onrechte het eerste algoritme voor een kwantumcomputer genoemd. Zo [...]

Lance Fortnow van de altijd interessante Computational Complexity blog maakte deze week een interessante observatie. Hij hoorde een aantal jaren geleden de volgende conversatie:
Physicist: Computer scientists have done nothing for quantum computing.
Computer Scientist: What about Shor’s quantum factoring algorithm?
Physicist: Peter Shor is a physicist.
De Peter Shor waarover het gaat is wel degelijk een computerwetenschapper. Zijn [...]