ppt/presentation.xml
ppt/slideMasters/slideMaster1.xml
ppt/slides/slide1.xml
ppt/slides/slide2.xml
ppt/slides/slide3.xml
ppt/slides/slide4.xml
ppt/slides/slide5.xml
ppt/slides/slide6.xml
ppt/slides/slide7.xml
ppt/slides/slide8.xml
ppt/slides/slide9.xml
ppt/slides/slide10.xml
ppt/slides/slide11.xml
ppt/slides/slide12.xml
ppt/notesMasters/notesMaster1.xml
ppt/commentAuthors.xml
ppt/presProps.xml
ppt/viewProps.xml
ppt/theme/theme1.xml
ppt/tableStyles.xml
ppt/slideLayouts/slideLayout1.xml
ppt/slideLayouts/slideLayout2.xml
ppt/media/image1.png
ppt/media/image2.png
ppt/theme/theme2.xml
ppt/notesSlides/notesSlide1.xml
ppt/media/audio1.wav
ppt/media/audio2.wav
ppt/media/image3.jpg
ppt/media/image4.jpg
ppt/media/image5.png
ppt/media/image6.webp
ppt/media/image7.png
ppt/media/image8.jpg
ppt/media/image9.jpg
ppt/notesSlides/notesSlide2.xml
ppt/media/image10.png
ppt/media/image11.png
ppt/media/image12.png
ppt/media/image13.png
ppt/media/image14.png
ppt/media/image15.png
ppt/media/image16.png
ppt/notesSlides/notesSlide3.xml
ppt/media/image17.png
ppt/media/image18.png
ppt/media/image19.png
ppt/notesSlides/notesSlide4.xml
ppt/notesSlides/notesSlide5.xml
ppt/media/image20.png
ppt/media/image21.png
ppt/notesSlides/notesSlide6.xml
ppt/media/image22.png
ppt/notesSlides/notesSlide7.xml
ppt/media/image23.jpeg
ppt/media/image24.emf
ppt/media/image25.jpeg
ppt/notesSlides/notesSlide8.xml
ppt/notesSlides/notesSlide9.xml
ppt/notesSlides/notesSlide10.xml
ppt/notesSlides/notesSlide11.xml
ppt/notesSlides/notesSlide12.xml
ppt/media/audio3.wav
ppt/media/audio4.wav
ppt/media/image26.png
ppt/media/image27.jpeg
ppt/changesInfos/changesInfo1.xml
ppt/revisionInfo.xml
docProps/core.xml
docProps/app.xml
ppt/media/image63.png
ppt/media/image64.png
_rels/.rels
ppt/_rels/presentation.xml.rels
ppt/slideMasters/_rels/slideMaster1.xml.rels
ppt/slides/_rels/slide1.xml.rels
ppt/slides/_rels/slide2.xml.rels
ppt/slides/_rels/slide3.xml.rels
ppt/slides/_rels/slide4.xml.rels
ppt/slides/_rels/slide5.xml.rels
ppt/slides/_rels/slide6.xml.rels
ppt/slides/_rels/slide7.xml.rels
ppt/slides/_rels/slide8.xml.rels
ppt/slides/_rels/slide9.xml.rels
ppt/slides/_rels/slide10.xml.rels
ppt/slides/_rels/slide11.xml.rels
ppt/slides/_rels/slide12.xml.rels
ppt/notesMasters/_rels/notesMaster1.xml.rels
ppt/slideLayouts/_rels/slideLayout1.xml.rels
ppt/slideLayouts/_rels/slideLayout2.xml.rels
ppt/notesSlides/_rels/notesSlide1.xml.rels
ppt/notesSlides/_rels/notesSlide2.xml.rels
ppt/notesSlides/_rels/notesSlide3.xml.rels
ppt/notesSlides/_rels/notesSlide4.xml.rels
ppt/notesSlides/_rels/notesSlide5.xml.rels
ppt/notesSlides/_rels/notesSlide6.xml.rels
ppt/notesSlides/_rels/notesSlide7.xml.rels
ppt/notesSlides/_rels/notesSlide8.xml.rels
ppt/notesSlides/_rels/notesSlide9.xml.rels
ppt/notesSlides/_rels/notesSlide10.xml.rels
ppt/notesSlides/_rels/notesSlide11.xml.rels
ppt/notesSlides/_rels/notesSlide12.xml.rels
[Content_Types].xml
Click to edit the title text format Click to edit the outline text format Second Outline Level Third Outline Level Fourth Outline Level Fifth Outline Level Sixth Outline Level Seventh Outline Level Eighth Outline Level Ninth Outline Level <
COSC1107 Computing Theory Analysing complexity Week 10 part 4 Week 10.4 Computing Theory james. .au * With thanks to Intro music ‘Far Over’ playing now … style.visibility ppt_x ppt_y ppt_x ppt_y style.visibility
Week 10.4 Computing Theory ‘Marvellous Machine’
Week 10.4 Computing Theory `Marvellous Machine’ “Counts grains of sand exactly within one second” “4,292,303,203,201,204 grains of sand” ?????? “Yeah? Well count this! style.visibility style.visibility style.visibility style.visibility
Week 10.4 Computing Theory `Marvellous Machine’ “4,292,303,203,201,204” “4,292,303,203,201,209” +5 “4,292,303,203,201,192” -12 “4,292,303,203,201,218” +14 “4,292,303,203,201,197” -7 style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
Week 10.4 Computing Theory `Marvellous Machine’ Machine has to pass numerous trials Failure at any time means machine fails acceptance test Trial 1 successful: Lucky guess! Trial 2 successful: Still just luck Trial 3 successful: Hmm… Trial 4 successful: ??? Trial 5 fails: GOTCHA! style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility
Week 10.4 Computing Theory `Marvellous Machine’ Trial 1 successful: Lucky guess! Trial 2 successful: Still just luck Trial 3 successful: Hmm… Trial 4 successful: ??? Trial 5 successful: So what’s the trick? Trial 6 successful: Really — what is it? Trial 7 successful: Now this is just getting boring … … Trial 47 successful: Alright! You win! It works ! style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility style.visibility ppt_x ppt_y style.visibility style.visibility style.visibility style.visibility
Probabilistic Algorithms Computing Theory Week 10.4 “Approximation method” for decision problems … Series of tests is applied If any test fails, the answer is ‘no’ Each successful test is ‘evidence’ for ‘yes’ More successful tests means more likelihood of ‘yes’ Can either return No (with certainty) Probably yes (usually with a specific probability) Less precision but much more efficient style.visibility ppt_x ppt_y style.visibility ppt_x ppt_y
Week 10.4 Computing Theory Primality Testing Given a number n Choose k such that 1 < k < n If n mod k = 0, halt with output ‘no’ If enough trials done then halt ‘ probably yes’ Go to step 1. How to choose k ? k = 2, 3, 5, 7, … n/2 (or √ n ) gives sieve of Eratosthenes (exponential) Smarter choice means less cases to test
Week 10.4 Computing Theory Probabilistic Primality Testing Testing for a strict subset of {2,3,5,7,..., √ n } can only ever give the result `probably prime' Trick is to make `good' choices of k Solovay -Strassen test: correctness probability after m trials is 1 – 1/2 m (!) Rabin-Miller test: correctness probability after m trials is 1 – 1/4 m (!!) Can have arbitrarily high correctness if we perform enough trials ....
RSA Pragmatics Computing Theory Week 10.4 Primality testing AKS algorithm says yes or no in polynomial time Solovay -Strassen test says probably yes or definitely no in much shorter time! Rabin-Miller test says probably yes or definitely no in much shorter time still! The trick is to increase the probability of correctness to almost 1 after a smallish number of steps … {5C22544A-7EE6-4342-B048-85BDC9FD1C3A} n SS(n) RM(n) 1 50% 75% 2 75% 94% 5 97% 99.9% 10 99.9% 99.9999% 25 99.999997% 99.999999999999% Any size number can be tested for primality in about 25 trials … (!!) style.visibility ppt_x ppt_y style.visibility style.visibility style.visibility
Week 10.4 Computing Theory RSA Properties Can be used for any encryption task Encryption and decryption speeds slow compared to secret key methods ( eg AES) Often used to distribute secret keys Used in SSH and similar tools Security depends on the size of the primes used 1024 to 4096 bits recommended, 2048 considered ‘safe’ Threats Factorisation being tractable Quantum computing (using Shor’s algorithm) Other public-key systems with shorter keys and more efficient encryption …
That’s it! Week 5 Computing Theory I am out of here! The lecture just halted. style.visibility ppt_y style.visibility ppt_y ppt_w ppt_h ppt_x ppt_y style.visibility ppt_w ppt_h ppt_x ppt_y style.visibility style.visibility ppt_w ppt_h ppt_x ppt_y ppt_w ppt_h style.rotation style.visibility style.visibility ppt_x ppt_y
‹#›
Click to edit Master title style Click to edit Master text styles Second level Third level Fourth level Fifth level <
Click to edit Master title style <
1 This cover slide full of examples of structures. Colour field to the right is discretised into cells we can identify by row and column. Need precision and agreed conventions to speak about cells in our algorithms and for making sense of the data values – here colour values held by cells. For example is cell indexed by 12 (x-axis) and 11 (y-axis) a blue colour value or not? Test it! Discrete Structures are not ‘Being’ but ‘Doing’. Well: are we starting to count from 0, or 1? Are we counting from the left top or left bottom or any other way? Look at the graph to the left. Graphs are central to many algorithms and models. And this course will get to graphs in more detail. Let’s say this is a model of evidence collected in a investigation. Vertices might represent persons of interest, edges strong evidence of communication between them in the last couple of months. A key investigative question might be, “has the person of interest communicated with the victim?” According to the evidence? Test it! P top left, V bottom right, say. How do we prove this claim?
2
3
4
5
6
7
8
9
10
11
12
PowerPoint Presentation 990 2018-02-27T21:31:56Z 2021-07-08T06:32:09Z
20344 956 Microsoft Office PowerPoint On-screen Show (4:3) 157 12 12 0 0 false Fonts Used 5 Theme 1 Slide Titles 12 Comic Sans MS StarSymbol Times Wingdings 1_Default Design COSC1107 Computing Theory Analysing complexity Week 10 part 4 ‘Marvellous Machine’ `Marvellous Machine’ `Marvellous Machine’ `Marvellous Machine’ `Marvellous Machine’ Probabilistic Algorithms Primality Testing Probabilistic Primality Testing RSA Pragmatics RSA Properties That’s it! false false false 16.0000