descrete log problems
you don't have a easy approach to solve the descrete log problems, so the algorithm is secure. the factorization problem is hard too.
Elgamal cryptographic system
\alpha -> a generator
\alpha^(q-1) -> 1
z_q*
random encryption - if you encypt it twice, maybe the different output :~ - but the value of random number doesn't matter decryption
real number complex number
inverse
associate rules
infinite field finite field
why is Zp a field?
the linear modulo equations
how to find a multiplicative inverse of an integer?
prime power
AES: use GF(z^8) as the sbox
constant: immediate
larger constant: use more instructions
lui: load upper immediate
in ARM case,
mov r0, 0x68000000
mov r0, 0x68, (LSL #24)
take a immediate but shift some zeroes to it
arguments
result values
temporaries
saved # must be saved by callee
$gp: global pointer (reg 28)
$sp: stack pointer (reg 29)
$fp: frame pointer (reg 30)
$ra: return address (reg 31)
there's no mov in MIPS...
use add 0 instead
try to map each arguments in registers, reduce the usage of stack (load/store)
arguments in $a0, $a1 ...
return value in $r0
local data allocated by callee procedure frame (activation record)
.data .code .symbol
most popular 32-bit instruction set in the world embedded core market
typical of many modern RISC ISAs
16x32-bit register file
32-bit data called "word" register: r1-r15
Data processing instructions
opcode Rd destination Rn source Operand2 immediate set condition -> reduce the usage of branches and jumps
pipelining
most constants are small
nop cost in ARM
blah
edge-triggered clocking
Latches and Flip-Flips
- change of state
- latches
- flip-flop
components for datapath
- instruction fetch
- R-type instructions
- memory and sign extension
the interface of R-type instructions
大家有沒有注意到，這邊有個 mux ，他的意思就是選擇器
I reload the page Orz
scheduler IRQ preemptive dispatcher
dispatch latency time it takes for the dispatcher to stop one process and start another
switching address space switching register and stack
- throughput
- high is better
- turnaround time
- lower is better
- response time
- lower is beter
- CPU utilization
- keep the CPU as busy as possible
- waiting time
- waiting in the ready queue
FCFS: first come, first serve
CPU burst / IO burst switching
FCFS convoy effect poor I/O utilization
SJF shortest job first non-preemptive / preemptive
but we don't know the real CPU burst shortest remaining time first (SRTF)
how to determining the length of next cpu burst - only estimate the time QQ
SJF is optimal! gain in short > lost of long
exponential average
is it good enough?
group do operations in field, groupm GF(p^k) galoa field polynomial how to find the multiplicative inverse
alu source
try to trace the ALU via simple instructions
memory 2 register mux
register destination mux
register file
register write enable
the opcode contains these enable/selection signals
if we don't need L2 cache, just disable it
beq instruction
PC = PC + 4 is the default behavior
but PC will be erased by branch instruction
if a language is context free, then some PDA recognizes it
finite field
- Euler's Theorem
- Euler's Totient Function
- Fermat's Theorem